Big-O With Change of Base for Log

[TheLegace]

Homework Statement

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)).

Homework Equations

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.

 

[Billy Bob]

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))

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).

 

[TheLegace]

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).

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 that's correct.

Thank You Very Much.
TheLegace.

 

[Billy Bob]

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

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.)