Let

$p(n) = \sum\limits_{i=0}^{d}a_in^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 \geq d$, then $p(n) = O(n^k)$.

In order to show $p(n) = O(n^k)$ we must show that there exist positive constants $c$ and $n_0$ such that:

$$\begin{equation} 0 \leq p(n) \leq cn^k \ \forall \ n \geq n_0 \\ 0 \leq \sum\limits_{i=0}^{d}a_in^i \leq cn^k \ \forall \ n \geq n_0 \\ 0 \leq a_0 + a_1n^1 + \cdots a_dn^d \leq cn^k \ \forall \ n \geq n_0 \\ 0 \leq a_0 + a_1n^1 + \cdots a_dn^d \leq \left( \sum\limits_{i=0}^{d}a_i \right)n^k \ \forall \ n \geq 1 \\ \end{equation}$$

Thus by setting $c = \sum\limits_{i=0}^{d}a_i$ and $n_0 = 1$ we conclude that $k \geq d \implies p(n) = O(n^k)$.

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

In order to show $p(n) = \Omega(n^k)$ we must show that there exist positive constants $c$ and $n_0$ such that:

$$\begin{equation} 0 \leq cn^k \leq p(n) \ \forall \ n \geq n_0 \\ 0 \leq cn^k \leq \sum\limits_{i=0}^{d}a_in^i \ \forall \ n \geq n_0 \\ 0 \leq cn^k \leq a_0 + a_1n^1 + \cdots a_dn^d \ \forall \ n \geq n_0 \\ 0 \leq a_kn^k \leq a_0 + a_1n^1 + \cdots a_dn^d \ \forall \ n \geq n_0 \\ \end{equation}$$

We do not need the entire summation, and can get away with setting $c = a_k$ to satisfy this inequality for all $n_0 \geq 1$. Therefore $k \leq d \implies p(n) = \Omega(n^k)$.

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

In a and b we showed that $p(n) = \Omega(n^k)$ and $p(n) = O(n^k)$ which is sufficient evidence that $p(n) = \Theta(n^k)$.

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

This is intuitive based on the proof in part a. Otherwise, we can use limits to formally prove this:

$$\begin{equation} \begin{split} \displaystyle{\lim_{n \to \infty}} \frac{p(n)}{n^k} & = \displaystyle{\lim_{n \to \infty}} \frac{\sum\limits_{i=0}^{d}a_in^i}{n^k} \\ & = \displaystyle{\lim_{n \to \infty}} \frac{n^d}{n^k} \\ & = 0 \end{split} \end{equation}$$

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

This is intuitive based on the proof in part b. Otherwise, we can use limits to formally prove this:

$$\begin{equation} \begin{split} \displaystyle{\lim_{n \to \infty}} \frac{p(n)}{n^k} & = \displaystyle{\lim_{n \to \infty}} \frac{\sum\limits_{i=0}^{d}a_in^i}{n^k} \\ & = \displaystyle{\lim_{n \to \infty}} \frac{n^d}{n^k} \\ & = \infty \end{split} \end{equation}$$