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 $\displaystyle f(n)$ be a polynomial of order $\displaystyle k$, that is $\displaystyle f(n)=b_{k}n^{k} + b_{k-1}n^{k-1} +...+ b_{0}$.

Prove that $\displaystyle f(n) = \Omega(n^{k})$.

Note: $\displaystyle b_{k} > 0$, but $\displaystyle b_{i}$ may be negative for $\displaystyle 0\le{i}<k$.

Hint: use the highest index for which $\displaystyle b_{s}< 0$.

[How can I prove that? and what is $\displaystyle b_{s}$???]

Re: Grow Rate and Big Omega of Polynomial

Quote:

Originally Posted by

**jfk** what is $\displaystyle b_{s}$???]

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

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

$\displaystyle 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 $\displaystyle |b_i|n^i\le b_kn^k/(k+1)$.