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} = sumlimits_{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_{ntoinfty} 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 -sumlimits_{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 sumlimits_{i=0}^{k-1} |a_{i}|n^i forall{n geq n_{0}}$ or $(a_{k}/2)n^k geq n^{k-1}sumlimits_{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 sumlimits_{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}sumlimits_{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
