CODEWITHSUNDEEP
complexity-theory
0implies0
0implies0

Reputation: 113

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

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, n0=1)

Upvotes: 1

Views: 249

Answers (3)

Utkarsh Singh
Utkarsh Singh

Reputation: 377

It's neither O(log n) nor O(n*log n). It'll be O(n) because for larger values of n log(n) is much smaller than n hence it'll be dropped.

Consider n=10000, now 5log(n) i.e 5*log(10000)=46(apprx) which is less than n/2(= 5000).

Upvotes: 0

Patrick87
Patrick87

Reputation: 28312

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?

Upvotes: 5

atin
atin

Reputation: 893

It's neither O(log n) nor O(n*log n). It'll be O(n) because for large value of n log n is much smaller than n hence it'll be dropped.

Upvotes: 1

Related Questions