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

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

  • 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