3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ your $c_2$ is not correct. $\endgroup$ – Denis Feb 4 '14 at 23:59
  • 1
    $\begingroup$ Sometimes, the definition is not the easiest way to prove something. $\endgroup$ – Raphael Feb 5 '14 at 0:10
  • 1
    $\begingroup$ @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.) $\endgroup$ – David Richerby Feb 5 '14 at 0:12
  • $\begingroup$ ah yes my bad. For the other way, you have to use $n^i/n^k\to 0$ if $i<k$. $\endgroup$ – Denis Feb 5 '14 at 1:34
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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. $$

$\endgroup$
1
$\begingroup$

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$).

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.