Results 1 to 4 of 4

Math Help - serious trouble finding big O

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    8

    serious trouble finding big O

    Original statement:

    f(n)=(n^3+4log_2 n)/(n+4)

    I'm sure the n+4 in both the denominator and numerator have something to do with it, but if i make nin the denominator a n^3, wouldn't that then make it smaller the the LHS?

    I'm suppose to prove

    f(n)=0(n^2)

    which means i need the inequality to make the RHS bigger than the LHS
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Roclemir View Post
    Original statement:

    f(n)=(n^3+4log_2 n)/(n+4)

    I'm sure the n+4 in both the denominator and numerator have something to do with it, but if i make nin the denominator a n^3, wouldn't that then make it smaller the the LHS?

    I'm suppose to prove

    f(n)=0(n^2)

    which means i need the inequality to make the RHS bigger than the LHS
    For n>1 (which makes everything of interest here positive):

    f(n)=\frac{n^3+4\log_2 n}{n+4}<\frac{n^3+4\log_2 n}{n}  =n^2+\frac{4 \log_2 (n)}{n}

    Then as \frac{4 \log_2 (n)}{n} \to 0 as n \to \infty for large enough n we have:

    \frac{4 \log_2 (n)}{n}<n^2

    So for large enough n :

    f(n)<2n^2

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2009
    Posts
    8

    thanks mate, just on one line...

    Thanks. All makes sense except that one line starting with "Then as... we have:", hate to be a noob, but can you please explain what you mean with the arrows and stuff thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Gamma's Avatar
    Joined
    Dec 2008
    From
    Iowa City, IA
    Posts
    517

    Beautiful CB, just filling in some details for him

    That notation means as n approaches infinity, \frac{4log_2(n)}{n} becomes arbitrarily close to 0. It is read the limit of \frac{4log_2(n)}{n} as n approaches infinity is 0.

    So given any \epsilon >0, there exists an integer N for which, |\frac{4log_2(n)}{n}|<\epsilon for all n>N.

    In particular, if \epsilon=1, there exists an N, such that for all n>N, \frac{4log_2(n)}{n}<1, this means we clearly have the identity \frac{4log_2(n)}{n}<1<n^2\Rightarrow n^2+\frac{4log_2(n)}{n}<n^2+n^2=2n^2.

    Thus |\frac{x^2+\frac{4log_2(n)}{n}}{n^2}|\leq 2 for all n>N. Which is the definition of f(n)=O(n^2)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Trouble Finding Derivative
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 17th 2011, 08:29 AM
  2. Having trouble finding this limit
    Posted in the Calculus Forum
    Replies: 4
    Last Post: September 14th 2011, 10:32 AM
  3. Having trouble finding x
    Posted in the Algebra Forum
    Replies: 5
    Last Post: July 9th 2011, 09:16 PM
  4. Having trouble finding domains...
    Posted in the Algebra Forum
    Replies: 3
    Last Post: September 13th 2009, 07:11 PM
  5. Trouble finding limits
    Posted in the Calculus Forum
    Replies: 19
    Last Post: April 7th 2008, 12:15 PM

Search Tags


/mathhelpforum @mathhelpforum