Problem 3.1

Asymptotic behavior of polynomials

Let

$$ p(n) = \sum_{i=0}^da_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.

1. If $k \geq d$, then $p(n) = O(n^k)$.
2. If $k \leq 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 $k < d$, then $p(n) = \omega(n^k)$.

This is very boring. I'm just going to examine half of one case, since everything else follows easliy from it.

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

$$ \sum_{i=0}^d = a_dn^d + a_{d-1}n^{d-1} + \ldots + a_1n + a_0 \leq cn^d $$

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

$$ c = a_d + b \geq a_d + \frac{a_{d-1}}n + \frac{a_{d-2}}{n^2} + \ldots + \frac{a_0}{n^d} $$

Or:

$$ b \geq \frac{a_{d-1}}n + \frac{a_{d-2}}{n^2} + \ldots + \frac{a_0}{n^d} $$

If we choose $b = 1$, then we can choose $n_0$ to be:

$$ 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) \leq cn^d \quad \text{for } n \geq 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's very similar to proove the other inequalities.