Results 1 to 4 of 4

Math Help - prove f(n) = Ѳ(n)

  1. #1
    Junior Member
    Joined
    Jun 2010
    Posts
    69

    prove f(n) = Ѳ(n)

    I need to prove that f(n) = Ѳ(n)

    when f:N -> R defined by
    \frac{n^2+2log2n}{n+1}

    <= since log2n<=n

    (I left out these works)

    = 6n for n>0


    since each term >= 0
    >= since log2n is >= 0 for n>=1

    >=  \frac{n^2}{n+n}
    = \frac{n}{2} for n>0

    Therefore f(n) = Ѳ(n)


    is it ok?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    For the first part, I would just go with

    \frac{n^{2}+2n}{n+1}\le\frac{n^{2}+2n+1}{n+1}=\fra  c{(n+1)^{2}}{n+1}=n+1\le 2n.

    It's a sharper bound, if you care for such things.

    Assuming the steps you've left out are valid, it looks ok to me.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2010
    Posts
    69
    Thanks Ackbeet, I'm really learning a lot of little extras from posting on this forum, things that are not covered in my lecture notes.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    A Plied Mathematician
    Joined
    Jun 2010
    From
    CT, USA
    Posts
    6,318
    Thanks
    4
    Awards
    2
    You're welcome. Have a good one!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove a(AB)=(aA)B=A(aB) ..
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2010, 04:14 AM
  2. Prove: f is one-to-one iff f is onto
    Posted in the Discrete Math Forum
    Replies: 12
    Last Post: June 25th 2010, 10:02 AM
  3. Replies: 2
    Last Post: August 28th 2009, 02:59 AM
  4. Please prove
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: April 7th 2009, 01:58 PM
  5. Prove this .
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: February 18th 2009, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum