Results 1 to 3 of 3

Math Help - Simple log question for algorithm

  1. #1
    Pan
    Pan is offline
    Newbie
    Joined
    May 2008
    Posts
    10

    Simple log question for algorithm

    I'm terrible with logs (just can't get my head around them).

    The question is about big-O notation but the part I don't understand is about logarithms.

    I've been told the following:
    \log_3 N = O(\log_2 N) because \log_3 N = \log_3 2 \times \log_2 N.

    I don't understand why. Can someone go over the simple rules of why that is (the bit after "because")?

    And isn't the implication of that, that any \log_b N will be O(\log_2 N)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    skeeter's Avatar
    Joined
    Jun 2008
    From
    North Texas
    Posts
    11,621
    Thanks
    426
    Quote Originally Posted by Pan View Post
    I'm terrible with logs (just can't get my head around them).

    The question is about big-O notation but the part I don't understand is about logarithms.

    I've been told the following:
    \log_3 N = O(\log_2 N) because \log_3 N = \log_3 2 \times \log_2 N.

    I don't understand why. Can someone go over the simple rules of why that is (the bit after "because")?

    And isn't the implication of that, that any \log_b N will be O(\log_2 N)
    \log_3{2} \cdot \log_2{N} =

    change of base for the 2nd factor ...

    \log_3{2} \cdot \frac{\log_3{N}}{\log_3{2}} = \log_3{N}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Pan
    Pan is offline
    Newbie
    Joined
    May 2008
    Posts
    10
    Quote Originally Posted by skeeter View Post
    \log_3{2} \cdot \log_2{N} =

    change of base for the 2nd factor ...

    \log_3{2} \cdot \frac{\log_3{N}}{\log_3{2}} = \log_3{N}
    If you had log_b{N}

    Can it be made equal to \log_b{c} \cdot \log_2{N}, where c is just some number that doesn't change.

    In other words, any log can be made so that the dominant factor (for large N) is a base 2 log.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Simple primality testing algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 27th 2011, 08:33 AM
  2. Simple question on EM algorithm
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 25th 2011, 07:10 PM
  3. Simple algorithm for errors-in-variables problem?
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: May 11th 2010, 07:34 AM
  4. compiling a simple ranking algorithm
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: March 29th 2009, 09:03 PM
  5. Algorithm Question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: September 4th 2007, 03:29 AM

Search Tags


/mathhelpforum @mathhelpforum