Why is $n^n = O(2^{n^c})$?

Question

I read here that $n^n$ belongs to $\mathsf{EXPTIME}$. That would imply that $n^n = O(2^{n^c})$ where $O$ refers to Big O notation. I'm surprised that's the case since I actually thought that $n^n$ would grow faster.

How can I illustrate or (ideally prove) that $2^{n^c}$ grows faster than $n^n$?

Answer 1

since: $2^{log_{2}\left(n\right)}=n$, you can see that: $n^{n}=2^{n\cdot log_{2}(n)}$, which is smaller then $2^{n^{2}}$

Answer 2

Whenever you see a tower of exponentials, you should think about taking logs. In this case, $$n^n<2^{n^c}\Leftrightarrow n\log n<n^c\log 2\Leftrightarrow A\log n<n^{c-1},$$ where $A$ is some constant. So, for large $n$, $n^n<2^{n^c}$ as long as $c>1$ (once you know that $\log$ is sub-exponential), and $$n^n=O(2^{n^c})$$ for all $c>1$ (if $c\leq 1$ it should be clearly false).