Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By emakarov

Thread: Grow Rate and Big Omega of Polynomial

  1. #1
    jfk is offline
    Newbie jfk's Avatar
    Mar 2012

    Question 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}$???]
    Last edited by jfk; Apr 15th 2012 at 11:04 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Oct 2009

    Re: Grow Rate and Big Omega of Polynomial

    Quote Originally Posted by jfk View Post
    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)$.
    Thanks from jfk
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Jul 25th 2011, 09:46 AM
  2. exponential grow
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Mar 3rd 2009, 11:52 PM
  3. Big Oh and Big Omega
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 4th 2008, 12:01 AM
  4. Omega
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 20th 2008, 01:09 PM
  5. How long will it take $10K to grow to...
    Posted in the Business Math Forum
    Replies: 5
    Last Post: Mar 9th 2007, 06:15 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags

/mathhelpforum @mathhelpforum