A question about asymptotic notations

[BeginnerP]

I) 5 + log n >= n.c

II) n/2 >= n.c

III) n.(0,698) + 4>= n.c

(Omega notation)

I and II false, III is true. Why? Which values are true for this statements?

[icy1]

Can you explain "n.c" and "n.(0,698)" ? I haven't come across this... n dot constant?

Usually people talk about algorithm running time with notation like

O(1) fastest, constant time, like array access
O(log(n)) logarithmic, like binary search
O(n) linear, like single for loop
O(n log(n) ) like Quicksort
O(n²) quadratic, like nested for loop

[BeginnerP]

c constant, actually n(0,698) is log 5^n .They are the same things. Original question is here:
https://ibb.co/i8Fj17

and, I have one more question
https://ibb.co/mqzu17 I is false, II and III are true. Why? And, where do I find asymptotic notation examples like this questions? Thanks a lot.

[jonnin]

O(1) = n.c then.

if I understand what you said with your notation:

1) 5+log(n) is tied to the variable N. N.c is constant time, as we said? So variable time is >= constant time. This looks true to me, so either your answer key is wrong or your explanation is incomplete.

[icy1]

sigh... math. Let's see if I even remember how to do this... for the "Original question is here:" image

(I) n^log_n5 + log n in the set of O(n)
False, because the left-most term is possibly exponential. For the exponent, log_n5, this can be greater than 1 if n is 4, 3, or 2 for example. So you have exponential on the left and linear on the right. Is left in set of right? nope, False.

(II) Not sure on this one. Graphed on Wolfram Alpha and it looks like linear growth. Why is this false?

(III) left-most term can be simplified to n log(5), which is basically same as O(n) so True.

Next image.

(I) I guess if we log both sides, (n+1000)log5 in set of n log6. I suppose n plus an offset will never be in the set of n, so False.

(II) sqrt(n) on the left; that constant division doesn't really matter. This is logarithmic and so True.

(III) ( (1/3) * log n)² in the set of log 3n ? Not sure. They first one feels logarithmic, so maybe...?


What does all this have to do with C++ though o.O

[dhayden]

I. False. n^log_n5+log(n) = 5+log(n) which is Omega(log(n)).

II. True A little manipulation shows this is n*(1/log(100)) = n*k which is Omega(n).

III. True. That's n*log(5)+4 = n*k1 + k2 which is Omega(n)

And you thought all that pre-calculus math would never be useful. :)