[Math] Comparing the asymptotic growth of two exponential functions

asymptoticscalculusexponential functiongraph theory

I'd like to compare the asymptotic growth rates of two functions:

Cayley's formula for the number of trees on $n$ vertices: $n^{n-2}$

The number of possible graphs on $n$ vertices: $2^{n \choose 2} = 2^{(n^2-n)/2}$

We could simplify the comparison to $n^n$ as compared to $2^{n^2}$. Based on the context, I'm sure that $2^{n^2}$ must grow faster than $n^n$, but why is this the case?

Best Answer

We have $n^{n-2}=e^{(\log n)(n-2)}$ while the other is $e^{(\log 2)\frac{n(n-1)}{2}}$.

Note that $\frac{n(n-1)}{2}$ grows faster than $(\log n)(n-2)$. The exponential function dramatically increases the disparities in rate of growth.