CODEWITHSUNDEEP
big-ocomplexity-theory
Shane Hsu
Shane Hsu

Reputation: 8357

Comparing O((logn)!) and O(2^n)

I am having a hard time comparing these two functions,

(logn)!

and

2^n

Any good mathematical proof?

Upvotes: 0

Views: 309

Answers (2)

sve
sve

Reputation: 4356

You cannot compare O((logn)!) and O(2^n) since big O notation represents a set. O(g(n)) is the set of of all function f such that f does not grows faster than g, formally is the same is saying that there exists C and n0 such that we have |f(n)| <= C|g(n)| for every n >= n0. The expression f(n) = O(g(n)) is a shorthand for saying that f(n) is in the set O(g(n)). what we can do is check if 2^n=O((logn)!) or (log n)!=O(2^n) (note that it could be that both are not true). Luckily, if we use the Stirling approximation we get that 

log((logn)!) = (logn)*(log (logn)) - logn + O(log(log n)) = O(n*(log 2))

since n * cost grows faster than (logn)*(log (logn)) and (logn)*(log (logn)) is the leading term in (logn)*(log (logn)) - logn + O(log(log n)). So we get that log((logn)!) = O(log(2^n)) which is same as saying that (log n)! = O(2^n)

Upvotes: 1

mszymborski
mszymborski

Reputation: 1654

One can easily show that for sufficiently large n it holds that:

 log(n)! <= log(n)^{log(n)} <= n^{log(n)} = 2^{log^2(n)}

We can now only consider exponents of 2 in the 2^n and the expression above - n and log^2(n) respectively (we can do that since we consider only sufficiently large n and 2^x is strictly rising for positive x). It is sufficient to show that the limit below diverges to prove that log(n)! is, in fact, o(2^n):

lim[n -> inf] (n)/(log^2(n))

Now we apply L'Hospital rule:

= lim [n -> inf] `n/(2log(n))`

And again:

= lim [n -> inf] `n/(2)`

Which diverges to infinity.

Upvotes: 1

Related Questions