Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
Thanks. That clears things up. – danmane Dec 2 '12 at 23:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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