I'm confused if the following approach is mathematically correct

Suppose I have to prove $(\log n)! > n^a$, where $a$ is a constant

I can assume $n = 2^k$ which leads to $k! > c^k$, where $c = 2^a$

The conclusion is true since factorials have a higher rate of growth than exponentials.

My doubt is, is it correct to terminate the proof there and conclude $(\log n)! > n^a$, or should I extend the proof until I get a correct result in terms of $n$?

  • 1
    $\begingroup$ That would be fine, if you have proved beforehand that $k!$ grows faster than $c^k$ for any $c$. $\endgroup$
    – vonbrand
    Commented Feb 18, 2020 at 22:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.