Let

$p(n) = \sum_{i = 0}^d a_i n^i,$

where $a_d > 0$, be a degree-$d$ polynomial in $n$, and let $k$ be a constant. Use the definitions of the asymptotic notations to prove the following properties.

a. If $k \ge d$, then $p(n) = O(n^k)$.

b. If $k \le d$, then $p(n) = \Omega(n^k)$.

c. If $k = d$, then $p(n) = \Theta(n^k)$.

d. If $k > d$, then $p(n) = o(n^k)$.

e. If $k < d$, then $p(n) = \omega(n^k)$.

Let's see that $p(n) = O(n^d)$. We need do pick $c = a_d + b$, such that

$\sum\limits_{i = 0}^d = a_d n^d + a_{d - 1}n^{d - 1} + \cdots + a_1n + a_0 \le cn^d.$

When we divide by $n^d$, we get

$c = a_d + b \ge a_d + \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.$

and

$b \ge \frac{a_{d - 1}}n + \frac{a_{d - 2}}{n^2} + \cdots + \frac{a_0}{n^d}.$

If we choose $b = 1$, then we can choose $n_0$,

$n_0 = \max(da_{d - 1}, d\sqrt{a_{d - 2}}, \ldots, d\sqrt[d]{a_0}).$

Now we have $n_0$ and $c$, such that

$p(n) \le cn^d \quad \text{for } n \ge n_0,$

which is the definition of $O(n^d)$.

By chosing $b = -1$ we can prove the $\Omega(n^d)$ inequality and thus the $\Theta(n^d)$ inequality.

It is very similar to prove the other inequalities.