Search code examples
algorithmtime-complexitybig-ocomplexity-theoryasymptotic-complexity

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

Solution

  • 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