I would like to know how $\binom {n}2 = \dfrac{n^2}{2}$ works out while I'm reading a proof on this page.
I have tried several ways, but I couldn't. i.e.
we knew that combinatorics formula that says, $\binom {n}2 = \dfrac{n!}{2! (n - 2)!} = ?$ the problem is that I don't how to get off from the binomial coefficient.
I went to Stirling's formula which says approximately, $n! \sim \sqrt{2 \pi n}{(\dfrac{n}{e})}^n = {(2\pi n)}^\dfrac{1}{2}{(\dfrac{n}{e})}^n$ since $n^n > e^n$, therefore $\dfrac{n^n}{e^n}$ goes bigger as n approaches to infinity. I don't know also how to simplify this into more small parts ..
Rosen in his book "Discrete Mathematics and Its Applications" [Rosen07, P.151] says that "factorial function grows extremely rapidly as n grows"; So, I try to connivance myself from this page that $\binom {n}2 = \dfrac{n^2}{2}$ but I couldn't get it. Also, I know why this is true since the factorial function grows very quickly as n grows, so it is obviously not polynomial, instead it is exponential algorithm as it seems. So, why the lower bound is $O(n^2)$ "polynomial" and not "exponential"?
Thank you.
They are not equal; ${n \choose 2} = \frac{n(n-1)}{2}$. But the difference between them is $n/2$, which is small enough that it can be rolled into the correction term in your link.