Time complexity - Prove $\binom{n}{3} = \theta(n^3)$

Question

$\binom{n}{3} = \frac{n!}{6(n-3)!}= \frac{n (n-2)(n-1)}{6}=t(n)$

Proving upper bound $O(n^3)= t(n) \leq c*n^3$

$\frac{n (n-2)(n-1)}{6} = \frac{n^3-2n^2+2n}{6}\leq n^3+2n \leq n^3+2n^3\leq 3n^3$

then $c=3, n=1$

My question is why did they made the expression more bigger and based on what?

Answer 1

Typically, in time complexity in comp sci classes, you can just drop the lower ordered terms.

As for the proof: the goal is to have a function that's $cn^h$. The resulting expression from your calculation is $\frac{n^3-2n^2+ 2n}{6}$ and not in the format we want. While it may be obvious that the numerator is a cubic polynomial and hence you can just say it's $\leq cn^3$, they show the rigorous process at arriving at that conclusion.

So let's start manipulating it with inequalities. Since it's divided by 6, it's $\leq$ than just the numerator by itself. $n^3-2n^2 + 2n \leq n^3+2n$ since $n$ is positive. $n^3 +2n \leq n^3 + 2n^3 = 3n^3 \leq cn^3$