Results 1 to 5 of 5

Math Help - Upeer and Lower bouds of big O

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    Upeer and Lower bouds of big O

    Is my working of this problem ok?

    f:N->R

    f(n) = \frac{n^2+2log2n}{n+1}<br />
    prove f(n) = O(n) < - - - thats big O with a "-" in it

    |f(n) | = |\frac{n^2+2log2n}{n+1}|
    = \frac{n^2+2+log2n}{n+1} since each term is >=0

    <= \frac{n^2+2n}{n+1} since log2n<=n

    <= \frac{n^2+2n^2}{n+1} since n>=1

    = \frac{3n^2}{n+1}
    = \frac{3n}{1}
    =3n



    f(n)  = \frac{n^2+2log2n}{n+1} since each term >= 0
    >= \frac{n^2}{n+1} since log2n is >= 0 for n>=1
    = \frac{n}{1}
    =n

    Therfore
    f(n) = O(n)

    I really hope i am doing this correctly
    Thanks for any help and input.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    More simple and powerful is to devide nunerator and denominator by n obtaining...

    f(n) = \frac{n^{2} + 2\ \ln 2n}{n+1} = \frac{n + 2\ \frac{\ln n}{n}}{1+\frac{1}{n}} (1)

    ... so that is...

    \lim_{n \rightarrow \infty} \frac{f(n)}{n} = 1 \rightarrow f(n) \sim n _ {n \rightarrow \infty} (2)

    Kind regards

    \chi \sigma
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    thanks for the help Chisigma, but what is more simple to you seems a step beyond what I am learning at the moment (I think).
    I just tried to answer the problem as close to the example solutions I had studied. We didn't divide the numerator, just worked it out in the style I have above.
    I am VERY new to discrete maths, is my attempt at the solution completely incorrect then? or even close?
    Last edited by dunsta; June 30th 2010 at 06:11 PM. Reason: need to know if I am completely wrong?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Hi, Can someone look at my original post, (even though I spelled "upper" incorrectly").
    Chisigma gave me an answer I don't really understand. She said " a more simple and powerful...." but I don't know if this implies my attempt was ok, but could be better done, or if my attempt was wrong.
    But I need to know if my attempt at the solution was way off, or good enough.

    Thanks for any help/input
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    A few comments:

     \frac{3n^2}{n+1}\neq 3n , but  \frac{3n^2}{n+1} \leq \frac{3n}{n-\frac12n}=6n for  n>0

     \frac{n^2}{n+1}\neq n , but  \frac{n^2}{n+1} \geq \frac{n^2}{n+n}=\frac n2 for  n>0

    Also you don't need to find a lower bound, unless you're trying to show  f(n)=\Theta(n) .

    Your first argument shows  f(n)=O(n) and your second argument shows  f(n)=\Omega(n) .
    Last edited by chiph588@; July 1st 2010 at 12:21 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Lower bounds
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 18th 2011, 04:59 PM
  2. Upper Lower Sum
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: March 10th 2011, 08:17 PM
  3. Lower sum for partition
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: April 10th 2010, 02:19 PM
  4. Greatest lower bound and lower bounds
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 13th 2009, 03:26 PM
  5. Lower bound
    Posted in the Advanced Math Topics Forum
    Replies: 1
    Last Post: May 9th 2006, 01:42 PM

Search Tags


/mathhelpforum @mathhelpforum