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}\]