0
$\begingroup$

I can't figure this out; is $2^{n^2}=O(n!)$ or is it the other way around? Any help is appreciated!

$\endgroup$
2
  • $\begingroup$ If you go from n to n+1, what is n! multiplied with, and what is 2^(n^2) multiplied with? $\endgroup$
    – gnasher729
    Commented Jan 25, 2022 at 21:56
  • $\begingroup$ for a quick intuition, try substituting some sufficiently large value and compare them. $\endgroup$
    – Rinkesh P
    Commented Jan 26, 2022 at 7:42

2 Answers 2

5
$\begingroup$

$$n! = 1\times 2\times … \times n \leqslant n \times n\times… \times n = n^n \leqslant (2^n)^n = 2^{n^2}$$

$\endgroup$
1
$\begingroup$

You can compare with their logarithm, since O(log(n!)) = O(nlogn) and O(log(2^(n^2)) = O(n^2) and nlogn < n^2. So the later one grows faster.

$\endgroup$
2
  • $\begingroup$ Obviously be careful if the expressions for the logarithms are closer together. $\endgroup$
    – gnasher729
    Commented Jan 26, 2022 at 14:02
  • $\begingroup$ Big-O of the original expressions are the same if the logarithms differ at most by a constant. In this case, the difference between n log n and n^2 is more than any constant, so 2^(2^n)) is asymptotically larger than n! $\endgroup$
    – gnasher729
    Commented Jan 26, 2022 at 19:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.