1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big-O With Change of Base for Log

  1. Jul 12, 2009 #1
    1. The problem statement, all variables and given/known data
    Hi, I am trying to prove for a>1, b>1 that f(x) = O(log_b(x)) then f(x) = O(log_a(x)).
    [Hint: log_b(x) = log_a(x)/log_a(b)).

    2. Relevant equations


    3. The attempt at a solution
    Assuming |f(x)| <= C|log_b(x)| true for x>k,
    then,
    f(x) <= log_a(x)/log_a(b)| for all x>1, C=1
    then,
    log_a(b)*f(x) <= log_a(x) all x>1 C= 1/log_a(b)
    f(x) <= log_a(x) x>1 C=1/log_a(b)
    f(x) is O(log_a(x))


    Now here comes my problems with most big-O problems, since the right side is being divided by something I should just multiply it out to other side:

    log_a(b)*f(x) <= log_a(x) I know that log_a(b) on left side would not matter except that it might be
    C= 1/log_a(b) and k =1

    According to my textbook/notes, C = 1/log_a(b), I still do not see why though, because if I multiply both sides by log_a(b) why C is like dividing both sides log_a(b), if someone could explain it, I would appreciate it thank you very much.


    Please Let me Know if this correct, thank you very much.

    TheLegace.
     
  2. jcsd
  3. Jul 13, 2009 #2

    Sorry, I don't follow that list of inequalities at all.

    Can you try it more clearly, perhaps like this.

    Given: There exist C and k such that |f(x)| < C |log_b (x)| for all x > k.

    Prove: There exist C' and k' such that |f(x)| < C' |log_a (x)| for all x > k'.

    Your k' can be the same as k. Your C' will be expressed in terms of C and log_a (b).
     
  4. Jul 13, 2009 #3

    Ok...
    Prove : a>1, b>1
    f(x) = O(log_b (x)) then f(x) = O(log_a (x))

    |f(x)| < C |log_b (x) | for all x>k
    |f(x)| < |log_a (x) / log_a (b) | for all x>1

    then f(x) = O(log_b (x)) = O(log_a (x)) when k=1 C=1/log_a (b)
    I am just hoping to know if thats correct.

    Thank You Very Much.
    TheLegace.
     
  5. Jul 13, 2009 #4
    I don't know how you are obtaining the last line quoted. It is invalid reasoning.

    Example:

    Let a=10, b=e. Use ln x to denote log base e of x, and let log x denote log base 10 of x.

    Let f(x) = 1 + 4 ln x.

    Then f is O(ln x), because f(x) < 5 ln x when x > 3. (C=5, k=3.) (Verify with a graph if you want.)

    Your next step says f(x) < log x / log e for x > 1. There is no reason for this to be true, and in fact it is false. (Verify with a graph if you want.)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Big-O With Change of Base for Log
  1. Big O (Replies: 7)

  2. Big-O Definition (Replies: 4)

Loading...