Results 1 to 4 of 4

Math Help - Big Oh Notation Proof

  1. #1
    Newbie
    Joined
    Mar 2011
    Posts
    2

    Big Oh Notation Proof

    I have been given the question. Show that f(n) = ((n^3)+(7n^2))/(n^2 - 14) = O(n)
    I know how to prove for a general
    //Linear Function
    //Consider f(n) = 5n + 4. When n >= 4,
    //5n + 4 <= 5n + n <= 6n.
    //So f(n) = O( n ) [i.e., c = 6 and n0 = 4].

    but this question baffles me, please anyone help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    ((n^3)+(7n^2))/(n^2 - 14) <= ((n^3)+(7n^2))/(n^2 - n) = {n^2(n+7)}/{n(n-1)} = {n(n+7)}/{n-1} <={2n^2}/{n-1} = 2n + 2n/{n-1}<=3n (for n>7)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Mar 2011
    Posts
    2
    Quote Originally Posted by Also sprach Zarathustra View Post
    ((n^3)+(7n^2))/(n^2 - 14) <= ((n^3)+(7n^2))/(n^2 - n) = {n^2(n+7)}/{n(n-1)} = {n(n+7)}/{n-1} <={2n^2}/{n-1} = 2n + 2n/{n-1}<=3n (for n>7)

    Thankyou for your Help, I have a small question regarding 2n + 2n/{n-1}<=3n

    is it 2n + (2n/(n-1)).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by MathsKid View Post
    Thankyou for your Help, I have a small question regarding 2n + 2n/{n-1}<=3n

    is it 2n + (2n/(n-1)).
    Yes.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A simple big-O notation proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 17th 2011, 05:49 AM
  2. Replies: 1
    Last Post: March 10th 2011, 03:23 AM
  3. Replies: 1
    Last Post: August 26th 2009, 01:40 PM
  4. sum notation
    Posted in the LaTeX Help Forum
    Replies: 3
    Last Post: May 3rd 2009, 03:02 PM
  5. Replies: 6
    Last Post: September 2nd 2008, 04:49 PM

Search Tags


/mathhelpforum @mathhelpforum