3-1 Asymptotic behavior of polynomials

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_i n^i = 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.