Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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)$.
