- #1
TheLegace
- 27
- 0
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.