0
$\begingroup$

[HOMEWORK, help and explanation will be more appreciated than the solution]

Hi I need some help proving that a general polynomial $\sum_{ i=0 }^{ k }{ { b }_{ i }{ n }^{ i }}=\Omega(n^{k})$ while some of the coefficients might be negative, in exception of $b_{k}>0$. I was thinking that as in the general case I could do the following $c\cdot(n^{k})\le|\sum_{ i=0 }^{ k }{ { b }_{ i }{ n }^{ i }}|=\sum_{ i=0 }^{ k }{ { b }_{ i }{ n }^{ i }}\le\sum_{ i=0 }^{ k }{ |{ b }_{ i }|\cdot|{ n }^{ i }|}$ but now I'm stuck and I don't know how to go on...

  • 1
    The notation $\Omega(n^k) \leq \sum \ldots$ is incorrect, in fact $2^n = \Omega(n^k) \nleq \sum_i^k n^i$.2012-04-15
  • 0
    sorry I'll edit the post to correct that, thanks @dtldarek2012-04-15
  • 0
    Could you tell me any constants $c$ and $n_0$ such that $n^5-100n^4 \geq c\cdot n^5$? Are $n_0 + 2$ or $c/2$ also good constants? What about $n^k-100n^{k-1}$ (make $c$ and $n_0$ dependent on $k$)? Finally, what is the limit of your sum $\sum_i^k b_i n^i$ as $n$ tends to infinity and why it is not negative infinity ;-) ?2012-04-15
  • 0
    e.g: c=0.5 and $n_{0}=200$, but I still don't see the big picture...2012-04-15
  • 0
    Would $c = 0.999$ be alright (how large $n_0$ you would need)? Try rewrite it as $(1-c)n^5 \geq \ldots$. What about other questions? Also, if $f_1(n) \geq c_1\cdot g(n)$ for $n > n_1$ and $f_2(n) \geq c_2\cdot g(n)$ for $n > n_2$, then what are the constants for $f_1+f_2 \geq c_+ \cdot g$?2012-04-15

2 Answers 2

1

Do you already know that if $p$ is a polynomial of degree $k$, then $p(n)$ is $O(n^k)$? If so consider writing your polynomial as

$$\sum_{i=0}^kb_in^i=b_kn^k-\left(-\sum_{i=0}^{k-1}b_ix^i\right)\;.$$

An alternative approach is to consider $$\lim_{n\to\infty}\frac1{n^k}\sum_{i=0}^kb_in^i\;.$$

Added: A third approach is to show that $n^k$ is $\displaystyle O\left(\sum_{i=0}^kb_in^i\right)$.

  • 0
    but the last one converges to 0...? then it's not low bounded by $n^{2}$ is't it?2012-04-15
  • 0
    @Janos: No, it doesn’t converge to $0$. Example: If your polynomial is $3x^3-100x^2$, you’re looking at the limit of $$\frac{3x^3-100x^2}{x^3}=3-\frac{100}x$$ as $n\to\infty$; what is that limit?2012-04-15
  • 0
    That will be 3. However I don't know how to calculate it in my case .2012-04-15
  • 1
    @Janos: Do the same thing: $$\frac1{n^k}\sum_{i=0}^kb_in^i=\sum_{i=0}^kb_in^{i-k}=b_k+\sum_{i=0}^{k-1}b_in^{i-k}\;,$$ so the limit is?2012-04-15
  • 0
    Well in this case $b_{k}$ will be the limit. However how can I know what are the the values of $c$ and $n_{0}$ in this case?2012-04-16
  • 1
    @Janos: Since $b_k$ is the limit, by definition of limit there is an $n_0$ such that $$\frac1{n^k}\sum_{i=0}^kb_in^i>\frac{b_k}2$$ whenever $n\ge n_0$. You can use that $n_0$ and $c=\frac{b_k}2$.2012-04-16
0

Here a short proof that this general polynomial = $O(n^k)$:

Suppose $f(n) = b_kn^k+b_{k-1}n^{k-1}+...+b_1n+b_0$

let $a = max_i${b}

$f(n) ≤ an^k+an^{k-1}+...+an+a≤(k+1)an^k≤cn^k$

for $c=(k+1)a$

I think that in order to prove $Ω(n^k)$ you only need to pick $c=(k+1)d$ , $d$ =$min_i${b}.

  • 0
    Except that that may give you a negative $c$.2012-04-15