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

Problem Detail: 

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?

Asked By : ask

Answered By : ask

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21298