# Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?

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?

• Because $$\binom{n}{k} = \frac{n^{\underline{k}}}{k!}$$, in your particular case $$\binom{n}{2} = \frac{n (n - 1)}{2!} = O(n^2)$$. – vonbrand Sep 5 '15 at 15:55

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$.

$\Theta$-notation more generally refers to the growth of a function. In terms of computational complexity this function can be done in $O(1)$ as:

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

Since there are a finite number of multiplications and multiplication is sometimes treated as $O(1)$ this has constant computational time. But, the author is not referring to the computational complexity of this function. Instead he is referring to the growth of the function:

$$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \in \Theta(n^2)$$

With the function $f(n) = {n \choose 2}$, it is the case that $f(n) = \frac{n(n-1)}{2} = \frac{1}{2}(n^2 - n) = \Theta(n^2)$. The function itself grows quadratically. Computing it actually only takes one multiplication operation, one subtraction, and one division by 2, so computing $f(n)$ can be done in $O(1)$ (assuming constant-time arithmetic operations).

To illustrate the difference -- the travelling salesman problem has $n!$ different paths, so the naive solution has a runtime of $O(n!)$. But computing $n!$ can be done $n$ multiplications.