# Time Complexity: Why does $n^n$ grow faster than $n!$?

Seeing the title, you will probably like to give your explanation as

$$n!=n\times (n-1)\times (n-2)\times (n-3)\times\cdots\times 1$$

where as

$$n^n$$ = $$n\times n \times n\times n \times\cdots\times n$$ $$\text{(n-times)}$$

but consider one thing: if we do $$\log(n!)$$ then it comes out to be $$O(n\log n)$$. On the other hand, if we do $$\log(n^n)$$ it also comes out to be $$O(n\log n)$$. So, aren't they equal asymptotically?

• Yes, both $\log n!$ and $\log n^n$ are equal asymptotically, but not $n!$ and $n^n$. – zdm Nov 25 '19 at 18:11

The core source of your confusion is that you have assumed that the asymptotic behavior of functions is closed under taking $$\log$$, which is false. There are countless examples, take: $$f(n)=n^{100}, \quad g(n)=n$$ If you take their logarithm they become: $$\log f(n) = 100 \log n,\quad \log g(n) = \log n$$ So their logarithms are both linear in $$\log n$$, while it's obvious they do not have a similar growth rate. Another example can be: $$f(n)=\exp(2 n), \quad g(n)=\exp(n)$$ and their logarithms are: $$\log f(n) = 2n, \log g(n) = n$$ You can see that $$f(n) = g(n)^2$$ and it has faster growth rate, but both their logarithms are linear in $$n$$. The intuitive reason is that, when you compare $$\log f(n)$$ and $$\log g(n)$$, you are basically comparing their exponents. Showing that the exponents of two functions have a similar growth rate is not the same as showing that the functions have the same growth rate.
In case you are wondering, the reversed direction would actually hold most of the time: If $$\log f(n)$$ grows faster than $$\log g(n)$$, and $$g(n)=\Omega(1)$$, then $$f(n)$$ grows faster than $$g(n)$$, and the condition $$g(n)=\Omega(1)$$ prevents cases like $$f(n) = \exp(1/n), g(n) = \exp(1/n^2)$$.
The first part is right. But you have a wrong conclusion! If $$g(n) = \Theta(f(n))$$, you cannot say for $$every$$ function $$h(n)$$, $$h(g(n)) = \Theta(h(f(n))$$.
For the case, we know that $$\log(n!) = \Theta(n\log(n))$$, but you can not conclude that it is also true if we apply $$h(n) = e^n$$ over the functions. In your case, intuitively, the main difference in $$\log$$ cases and exponential cases is we sum limits in $$\log$$ cases and multiply limits in the exponential case!
• @HIRAKMONDAL indeed using $O$ notation here definitely wrong! $1$ is in $O(n)$ and $n$ is $O(n)$. Definitely you cannot conclude that $1$ and $n$ are asymptotically the same! – OmG Nov 25 '19 at 12:25