Asymptotic behavior of polynomials

Let

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.

1. If $k \ge d$, then $p(n) = O(n^k)$.
2. If $k \le d$, then $p(n) = \Omega(n^k)$.
3. If $k = d$, then $p(n) = \Theta(n^k)$.
4. If $k > d$, then $p(n) = o(n^k)$.
5. If $% $, then $p(n) = \omega(n^k)$.

1. Asymptotic Upper Bound

To show that $p(n) = O(n^k)$ when $k \ge d$, we have to show there exists constants $c, n_0 > 0$ such that $0 \le p(n) \le c \cdot n^k$ for all $n \ge n_0$.

The last line follows from the fact that as $k \ge d$, for all possible values of $i$, $(i - k) \le 0$, i.e. all $n^{i - k}$ will be less than or equal to 1 for all $n \ge 1$.

So we can say that $0 \le p(n) \le c \cdot n^k$, where $c = \sum_{i = 0}^d a_i$ and $n_0 = 1$.

Hence, $p(n) = O(n^k)$.

2. Asymptotic Lower Bound

To show that $p(n) = \Omega(n^k)$ when $k \le d$, we have to show there exists constants $c, n_0 > 0$ such that $0 \le c \cdot n^k \le p(n)$ for all $n \ge n_0$.

So we can say that $0 \le c \cdot n^k \le p(n)$, where $c = a_k$ and $n_0 = 1$.

Hence, $p(n) = \Omega(n^k)$.

3. Asymptotic Bound

We have already proved that for $k = d$, $p(n) = O(n)$ and $p(n) = \Omega(n)$. Hence, $p(n) = \Theta(n)$.

4. Asymptotic Tight Upper Bound

We can easily prove this by removing the equality from the proof of 1.

Other than that we can use the limit definition of $o$-notation:

Hence, $p(n) = o(n)$.

5. Asymptotic Tight Lower Bound

We can easily prove this by removing the equality from the proof of 2.

Other than that we can use the limit definition of $\omega$-notation:

Hence, $p(n) = \omega(n)$.