# Grow Rate and Big Omega of Polynomial

• Apr 15th 2012, 10:21 PM
jfk
Growth Rate and Big Omega of Polynomial
Hello everybody,

I'm dealing with this problem already for a couple of days and I got really stuck, I just need to understand in plain English or Spanish (lol) how to deal with this problem.

Here is the problem:

Let $f(n)$ be a polynomial of order $k$, that is $f(n)=b_{k}n^{k} + b_{k-1}n^{k-1} +...+ b_{0}$.
Prove that $f(n) = \Omega(n^{k})$.
Note: $b_{k} > 0$, but $b_{i}$ may be negative for $0\le{i}.
Hint: use the highest index for which $b_{s}< 0$.

[How can I prove that? and what is $b_{s}$???]
• Apr 16th 2012, 04:21 AM
emakarov
Re: Grow Rate and Big Omega of Polynomial
Quote:

Originally Posted by jfk
what is $b_{s}$???]

The hint is to use the highest index $s$ for which $b_{s}< 0$.

My idea, rather, is to break $b_kn^k$ into k + 1 equal parts and to prove that each part is greater than $|b_i|n^i$ for all 0 <= i < k (starting from some n). Then even if all non-leading coefficients are negative,

$b_{k}n^{k}+\sum_{i=0}^{k-1}b_in^i \ge b_{k}n^{k}-\sum_{i=0}^{k-1}|b_i|n^i \ge b_{k}n^{k}-k\cdot b_{k}n^{k}/(k+1) =(b_{k}/(k+1))n^{k}$

So it is sufficient to find N such that for all 0 <= i < k and all n > N we have $|b_i|n^i\le b_kn^k/(k+1)$.