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

Thread: 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; Apr 16th 2012 at 12:04 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,573
    Thanks
    789

    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