World's most popular travel blog for travel bloggers.

[Solved]: Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?

, , No Comments
Problem Detail: 

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?

Asked By : PP121

Answered By : David Richerby

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback