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 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}<k.
    Hint: use the highest index for which b_{s}< 0.

    [How can I prove that? and what is b_{s}???]
    Last edited by jfk; Apr 16th 2012 at 12:04 AM.
    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 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).
    Thanks from jfk
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Jul 25th 2011, 10:46 AM
  2. exponential grow
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Mar 4th 2009, 12:52 AM
  3. Big Oh and Big Omega
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: May 4th 2008, 01:01 AM
  4. Omega
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jan 20th 2008, 02: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, 07:15 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags

/mathhelpforum @mathhelpforum