In Cormen's Algorithms textbook, the author casually mentions that ${n \choose 2}$ is $\Theta(n^2)$.Why is this so? In the calculation$${n \choose 2} = \frac{n!}{(n-2)!2!}$$there are $n$ multiplication operations in the numerator and $n$ multiplications in the denominator. That means there are at most $2n+1$ computations to here make (one for the division step), no?
Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?
asymptotics
You're assuming that $\Theta(\cdot)$ means something it doesn't mean. $\Theta(\cdot)$ is just a comparison between functions. It doesn't matter what those functions are being used to measure.Saying that $\binom{n}{2}=\Theta(n^2)$ means only that there are constants $c_1$ and $c_2$ such that, for all large enough $n$, $c_1n^2\leq\binom{n}{2}\leq c_2n^2$. It says nothing at all about how long it takes to compute the function $\binom{n}{2}$ for any value of $n$.For example, we can define a function $f(n) = n^2$ if the $n$th Turing machine terminates when started with no input and $f(n)=n^2+1$ if it doesn't. The function $f$ isn't even computable but we still have $f=\Theta(n^2)$ because, for all $n\geq 1$, $n^2\leq f(n)\leq 2n^2$.