How does $a^{a^n}$ compare with $n!$ asymptotically? I am learning Asymptotic complexity of functions from CLRS. I know that exponentiation functions like $a^n$,$(a>0)$ are faster than $n!$ But what about $a^{a^n}$ vs $n!$ How do they compare? A proof would really help me understand the concept. Thanks!
 A: How do they compare?: $n!=\mathcal{O}(a^{a^n})$
Proof:
If we bring down both $n!$ and $a^{a^n}$ to $log$ scale then $n!$ in $log$ scale will be approximately $nlogn$ (as $log(n!)≈nlogn$ using Stirling's approximation) and $a^{a^n}$ will be brought down to $a^n*loga$.
$nlogn$ grows slower than $a^n*loga$ which implies $n!=\mathcal{O}(a^{a^n})$.
A: 
Applying $\ln\circ\ln$ we   obtain
  \begin{align*}
\ln\left(\ln\left(a^{a^n}\right)\right)
&=\ln\left(a^n\ln    a\right)\\
&=\ln a^n+\ln\left(\ln\left(a\right)\right)\\
&=n\ln   a+\ln\left(\ln\left(a\right)\right)\\
&\sim n\ln  a\tag{1}
\end{align*}

Recalling Stirlings formula $n!\sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}$ we obtain

\begin{align*}
\ln\left(\ln\left(n!\right)\right)&\sim\ln\left(\ln\left(\left(\frac{n}{e}\right)^n\sqrt{2\pi n}\right)\right)\\
&=\ln\left(\ln\left(\frac{n}{e}\right)^n+\ln\sqrt{2\pi   n}\right)\\
&=\ln\left(n\ln n-n+\ln\sqrt{2\pi}+\ln n\right)\\
&\sim \ln\left(n\ln n\right)\tag{2}
\end{align*}

We conclude from (1) and (2)

\begin{align*}
\ln\left(n\ln n\right)=\mathcal{O}\left(n\ln  a\right)
\end{align*}
  from which
  \begin{align*}
\ln\left(\ln\left(n!\right)\right)=\mathcal{O}\left(\ln\ln    a^{a^n}\right)
\end{align*}
  and finally
  \begin{align*}
\color{blue}{n!=\mathcal{O}\left(a^{a^n}\right)}
\end{align*}
  follows.

