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

Math Help - Grow Rate and Big Omega of Polynomial

  1. #1
    jfk
    jfk is offline
    Newbie jfk's Avatar
    Joined
    Mar 2012
    From
    ...
    Posts
    23

    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; April 15th 2012 at 11:04 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,540
    Thanks
    780

    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: July 25th 2011, 09:46 AM
  2. exponential grow
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: March 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: January 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: March 9th 2007, 06:15 PM

Search Tags


/mathhelpforum @mathhelpforum