# How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive.

I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for all $n \geq n_0$.

The upper limit is easy to prove by taking $c_{2} = \sum\limits_{i=0}^k |a_i|$

I don't know how to prove the lower limit. Any hints?

• your $c_2$ is not correct. – Denis Feb 4 '14 at 23:59
• – Raphael Feb 5 '14 at 0:10
• @dkuper Yes it is. For $n>1$, $\sum_{i=0}^k a_in^i \le \sum_i a_in^k \le \sum_i |a_i|n^k = n^k\sum_i|a_i|$. (Well, OK, there's the typo in the summation limit but if that's what you were pointing out, it would have been better to just say that.) – David Richerby Feb 5 '14 at 0:12
• ah yes my bad. For the other way, you have to use $n^i/n^k\to 0$ if $i<k$. – Denis Feb 5 '14 at 1:34

I think I found a good way to prove $p(n) = \Omega(n^k)$:

We want to show that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

We know $\lim_{n\to\infty} p(n)/n^k = a_{k}$

This gives us some intuition to choose $c \leq a_{k}$.

Let $c = a_{k}/2$

Now choose $n_{0}$ such that $cn^k = (a_{k}/2)n^k \leq p(n)\ \forall{n \geq n_{0}}$.

or rearranging, $(a_{k}/2)n^k \geq -\sum\limits_{i=0}^{k-1} a_{i}n^i\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n^k \geq \sum\limits_{i=0}^{k-1} |a_{i}|n^i\ \forall{n \geq n_{0}}$

or $(a_{k}/2)n^k \geq n^{k-1}\sum\limits_{i=0}^{k-1} |a_{i}|n^{i-(k-1)}\ \forall{n \geq n_{0}}$

or we can relax the inequality and pick $n_{0}$ such that $(a_{k}/2)n \geq \sum\limits_{i=0}^{k-1} |a_{i}|\ \forall{n \geq n_{0}}$ since $n^{i-(k-1)} \leq 1$

Hence pick $n_{0} = 2/a_{k}\sum\limits_{i=0}^{k-1} |a_{i}|$

We now have a $c$ and $n_{0}$ such that $0 \leq cn^k \leq p(n)\ \forall{n \geq n_{0}}$

Hence proved.

Let \begin{align*} p(n) &=a_kn^k + \dots + a_0 \\ &= \tfrac12a_k n^k + \tfrac12a_k n^k + a_{k-1}n^{k-1} + \dots +a_{0}\\ &=\tfrac12a_kn^k + \left(\tfrac{a_k}{2k}n^k + a_{k-1}n^{k-1}\right) + \left(\tfrac{a_k}{2k}n^k + a_{k-2}n^{k-2}\right) + \dotsc\\ &\qquad + \left(\tfrac{a_k}{2k}n^k + a_{0}\right)\,. \end{align*}

Since $a_k>0$, we have, for all large enough $n$, \begin{align*} \tfrac{a_k}{2k}n^k + a_{k-1}n^{k-1} &\geq 0\\ \tfrac{a_k}{2k}n^k + a_{k-2}n^{k-2} &\geq 0\\ &\vdots\\ \tfrac{a_k}{2k}n^k + a_{0} &\geq 0\,. \end{align*}

Therefore, we have $p(n)\geq\tfrac12a_{k}n^k$ for all large enough $n$ (i.e., we can take $c=a_k/2$).

For the lower limit, use the fact that for $i > 0$, $\lim_{n\to\infty} n^{-i} = 0$. This means that for every $\epsilon > 0$ and $i > 0$ you can find $n_0$ such that for $n \geq n_0$, $n^{-i} < \epsilon$. Try to use this to prove that for every $\epsilon > 0$ there is $n_0$ such that for $n \geq n_0$, $$\sum_{i=0}^k a_i n^i \geq (a_k - \epsilon) n^k.$$

Assume $c_k$ > 0. Given the coefficients, show that there is an n > 0 such that $c_0·n^0$, $c_1·n^1$, ..., $c_{k-1}·n^{k-1}$ are all less than $(c_k·n^k)/(2n)$ (for each index you find a closed form expression for the smallest n). Then the polynomial is between $0.5·c_k·n^k$ and $1.5·c_k·n^k$.

We know that if the limit $$\lim_{n->\infty}\frac{f(n)}{g(n)}$$ exists and is strictly between zero and infinity, then $$f(n)\in\Theta(g)$$. In this case, we need to evaluate the limit $$\lim_{n->\infty}\frac{a_k n^k+a_{k-1}n^{k-1}+\cdots+a_1 n+a_0}{n^k}.$$ But this limit can be split into the $$k+1$$ limits $$\lim_{n->\infty}\frac{a_i n^i}{n^k},$$ where $$0\le i\le k$$. Each limit evaluates to zero for all $$i\ne k$$ and when $$i=k$$ the limit evaluates to $$a_k>0$$, so the polynomial is in $$\Theta(n^k)$$.