Results 1 to 4 of 4

Math Help - Big-Oh notation and a logarithmic function problem

  1. #1
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Big-Oh notation and a logarithmic function problem

    I need help with a problem I found in a Discrete Mathematics book.

    The problem is:

    Prove that the \lfloor{\log_{2} n}\rfloor + 1 is O(\log_{2} n) or \lfloor{\log_{2} n}}\rfloor + 1 is big-oh of \log_{2} n


    So according to the definition of Big-O notation we have to show that:

     \lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert


    Now what property of logarithm proves that:

     \lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert


    From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?
    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

    Re: Big-Oh notation and a logarithmic function problem

    Quote Originally Posted by x3bnm View Post
    I need help with a problem I found in a Discrete Mathematics book.

    The problem is:

    Prove that the \lfloor{\log_{2} n}\rfloor + 1 is O(\log_{2} n) or \lfloor{\log_{2} n}}\rfloor + 1 is big-oh of \log_{2} n


    So according to the definition of Big-O notation we have to show that:

     \lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert


    Now what property of logarithm proves that:

     \lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert


    From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?
    Say that  \lfloor{\log_{2}n}\rfloor=x. Then,

     \lvert{\lfloor{x}\rfloor + 1}\rvert \leq M * \lvert{x}\rvert

     \lvert{\lfloor{x}\rfloor + 1}\rvert \leq  \lvert{\lfloor{x}\rfloor + \lfloor{x}\rfloor}\rvert =2\lvert{x}\rvert
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Re: Big-Oh notation and a logarithmic function problem

    Quote Originally Posted by x3bnm View Post
    I need help with a problem I found in a Discrete Mathematics book.

    The problem is:

    Prove that the \lfloor{\log_{2} n}\rfloor + 1 is O(\log_{2} n) or \lfloor{\log_{2} n}}\rfloor + 1 is big-oh of \log_{2} n


    So according to the definition of Big-O notation we have to show that:

     \lvert{\lfloor \log_{2} {n} \rfloor + 1} \rvert \leq M * \lvert{\log_{2} n}\rvert


    Now what property of logarithm proves that:

     \lvert{\lfloor{\log_{2}n}\rfloor + 1}\rvert \leq M * \lvert{\log_{2}n}\rvert


    From my knowledge I can't find a way to prove this. Can anyone kindly help me with this?
    For n>2,\  0<\lfloor \log_2(n) \rfloor  \le \log_2(n)

    and: n>2,\  1 < \log_2(n)

    and since for n>2 everything is positive we have:

    n>2,\  |\lfloor \log_2(n) \rfloor+1| < 2|\log_2(n)|

    and Also.. beat me to it....

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member x3bnm's Avatar
    Joined
    Nov 2009
    Posts
    300
    Thanks
    16

    Re: Big-Oh notation and a logarithmic function problem

    Thanks Also sprach Zarathustra and CaptainBlack for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. logarithmic notation
    Posted in the Algebra Forum
    Replies: 12
    Last Post: November 27th 2011, 06:42 AM
  2. [SOLVED] Function Notation word problem
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 10th 2010, 05:14 PM
  3. Function notation problem
    Posted in the Algebra Forum
    Replies: 4
    Last Post: July 14th 2010, 08:50 PM
  4. Need Help with Logarithmic function problem???
    Posted in the Calculus Forum
    Replies: 10
    Last Post: April 5th 2010, 01:39 AM
  5. Logarithmic Function - Performance Problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: May 5th 2009, 02:30 AM

/mathhelpforum @mathhelpforum