1
$\begingroup$

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?

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

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

$\endgroup$
5
$\begingroup$

$\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)$$

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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