# Complexity of $\binom{n}{2}$

So:

$$\binom{n}{2} = \frac{n!}{2!(n-2)!}$$

Using Stirling's approximation we have:

$$\frac{\sqrt{2 \pi n}(\frac{n}{e})^n}{[\sqrt{2 \pi 2}(\frac{2}{e})^2][\sqrt{2 \pi (n-2)}(\frac{(n-2)}{e})^{(n-2)}]}$$

Removing constants and simplifying:

$$\frac{(\frac{n}{e})^n}{(\frac{(n-2)}{e})^{(n-2)}} = \frac{n^n}{e^n} \times \frac{e^{n-2}}{(n-2)^{n-2}} = \frac{n^n}{(n-2)^{(n-2)}}$$

Not sure how to proceed.

• $$\binom{n}2=\frac{n(n-1)}2$$ Jun 22 '15 at 21:21
• Can you show me the derivation? Jun 22 '15 at 21:22
• Stirling's approximation to compute $n(n-1)$? Are you joking? Jun 22 '15 at 21:23
• Funnily enough you nearly had it with your (rather convoluted) method: $$\frac{n^n}{(n-2)^{n-2}} \sim \frac{n^n}{n^{n-2}} = n^2$$ Jun 22 '15 at 21:42
• Well $$\frac{n^n}{(n-2)^{n-2}} = \frac{n^n}{n^{n-2}} \cdot \left( \frac{n}{n-2} \right)^{n-2}$$ And $\left( \frac{n}{n-2} \right)^{n-2} \to e^2$ as $n \to \infty$, which is constant. (I probably abused the $\sim$ symbol, but you catch my drift.) Jun 22 '15 at 22:00

$$\binom{n}{2} = \frac{n!}{2!(n-2)!} = \frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} = \mathcal{O}(n^2)$$