complexity theory - Why is O(n/2 + 5 log n) O(log n) and not O(n log n)?

Question

For n/2 + 5 log n, I would of thought the lower order terms of 5 and 2 would be dropped, thus leaving n log n

Where am I going wrong?

Edit:

Thank you, I believe I can now correct my mistake:

O(n/2 + 5 log n) = O(n/2 + log n) = O(n + log n) = O(n)

n/2 + 5 log n <= 2n, for all n >= 1 (c = 2, n₀=1)

question from:https://stackoverflow.com/questions/66046081/why-is-on-2-5-log-n-olog-n-and-not-on-log-n

Answer 1

Let us define the function f as follows for n >= 1:

f(n) = n/2 + 5*log(n)

This function is not O(log n); it grows more quickly than that. To show that, we can show that for any constant c > 0, there is a choice of n0 such that for n > n0, f(n) > c * log(n). For 0 < c <= 5, this is trivial, since f(n) > [5log(n)] by definition. For c > 5, we get

    n/2 + 5*log(n) > c*log(n)
<=> n/2 > (c - 5)*log(n)
<=> (1/(2(c - 5))*n/log(n) > 1

We can now note that the expression on the LHS is monotonically increasing for n > 1 and find the limit as n grows without bound using l'Hopital:

  lim(n->infinity) (1/(2(c - 5))*n/log(n)
= (1/(2(c - 5))* lim(n->infinity) n/log(n)
= (1/(2(c - 5))* lim(n->infinity) 1/(1/n)
= (1/(2(c - 5))* lim(n->infinity) n
-> infinity

Using l'Hopital we find there is no limit as n grows without bound; the value of the LHS grows without bound as well. Because the LHS is monotonically increasing and grows without bound, there must be an n0 after which the value of the LHS exceeds the value 1, as required.

This all proves that f is not O(log n).

It is true that f is O(n log n). This is not hard to show at all: choose c = (5+1/2), and it is obvious that

f(n) = n/2 + 5log(n) <= nlog(n)/2 + 5nlog(n) = (5+1/2)nlog(n) for all n.

However, this is not the best bound we can get for your function. Your function is actually O(n) as well. Choosing the same value for c as before, we need only notice that n > log(n) for all n >= 1, so

f(n) = n/2 + 5log(n) <= n/2 + 5n = (5+1/2)n

So, f is also O(n). We can show that f(n) is Omega(n) which proves it is also Theta(n). That is left as an exercise but is not difficult to do either. Hint: what if you choose c = 1/2?