CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomplexity-theoryasymptotic-complexity
Janaky Murthy
Janaky Murthy

Reputation: 60

Is log(n!) = O((log(n))^2)?

I am practicing problems on asymptotic analysis and I am stuck with this problem.

Is log(n!) = O((log(n))^2) ?

I am able to show that 

log(n!) = O(n*log(n)) 
(log 1 + log 2 + .. + log n <= log n + log n + ... + log n)

and

 (log(n))^2 = O(n*log(n)) 
(log n <= n => (log n)^2 <= n*logn )

I am not able to proceed further. Any hint or intuition on how to proceed further? Thanks

Upvotes: 0

Views: 3810

Answers (2)

Janaky Murthy
Janaky Murthy

Reputation: 60

I think I got the answer to my own question. We will prove the following facts:

1) n*log(n) is a tight bound for log(n!)

2) n*log(n) is a upper bound for (log(n))^2

3)n*log(n) is not a lower bound for (log(n))^2

For proof of (1) see this.

Proof(2) & (3) is provided in the question itself. growth rate of log n < growth rate of n. So growth rate of log(n)^2 < growth rate of n*log(n). So log(n)^2 = o(n*log(n)) (Here I have used little-o to denote that growth rate of n*log(n) is strictly greater than growth rate of log(n)^2

So the conclusion is that log(n!) = big-omega(log(n^2)) Correct me if I have made any mistake

Upvotes: 0

Nikhil Pathania
Nikhil Pathania

Reputation: 831

Accoriding to Stirling's Approximation:

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

So clearly upper bound for log(n!) will be O(nlogn)

Lower bound can be calculated by removing first half of the equation as:

log(1) + ... + log(n/2) + ... + log(n) = log(n/2) + ... + log(n)
= log(n/2) + ... + log(n/2)
= n/2 * log(n/2)

So Lower bound is also nlogn. Clearly answer would be NO

Upvotes: 3

Related Questions