base transformation rule significance in finding big o notation Recall the equivalence:
$$m=b^k \implies k = log_bm$$
as well as the base transformation rule:
$$log_am=(log_ab)(log_bm)$$
Are the following true or false?
(a) $log_2n$ is $O(log_3n)$
(b) $2^{log_2n}$ is $O(2^{log_3n})$
(c) $(log_2n)^2$ is $O((log_3n)^2)$

Solutions:
(a) True. $log_2n = (log_23)(log_3n)$ which is $O(log_3n)$
(b) False. $2^{log_2n}=n$ ... etc.
(c) True. $(log_2n)^2 = ((log_23)(log_3n))^2 = (log_23)^2(log_3n^2)$

my question is this, what is the significance of using the base transformation rule as in the first or third case, what does doing this rule tell us about whether the statement is true or false (for the first one how didthey come up with the first log of $log_23$, also i didn't even have to use the base transformation rule for the first one and just eye balled it, which gave me the correct answer) the third solution is really confusing me, what is the significance of doing the transformation and what does said transformation show us about whether the statement is true or not
 A: Let's look at just the first problem for now (I'll touch on the third one in a moment, but it's not terribly different except requiring more algebra).
You want to show whether or not $\log_2n$ is $O(\log_3n)$. I assume that you know, for example, that $5n^2$ is $O(n^2)$, because 5 is a constant (that is, it's just some fixed number), and when you do asymptotic analysis (like big O notation), you ignore such constants. This gives you a hint as to how to solve our problem. If you can show that $\log_2n$ is equal to some constant number times $\log_3n$, then you know that it is $O(\log_3n)$.
How can you do that? Well, you need to get a $\log_3n$ term floating around in the equation, so how do you convert $\log_2n$ to something with a $\log_3n$ in it? Just use the change of base rule that you wrote above: $log_am = (\log_ab)(\log_bm)$, plugging in the values $a = 2$, $b = 3$, and $m = n$. 
This gives you $log_2m = (\log_23)(\log_3n)$. But what is $\log_23$? It's just a number, really. You can plug it into a calculator or wolfram|alpha and see that it is about equal to 1.585. So what you have is something like $log_2m = 1.585 \cdot \log_3n$. Just as you ignored the 5 when doing the asymptotic analysis of the polynomial $5n^2$ above, so too will you ignore the $log_23 = 1.585$ here, which shows that $\log_2n$ is $O(\log_3n)$, just like you wanted.
In problem 3, the same thing is going on, except the constant that gets ignored at the end is $(\log_23)^2$ (which is approximately 2.512), and you have to do a little more algebra by moving around the square after you do the change of base.
The important lessons to draw here are:


*

*Solving a simpler problem can give you ideas about how to solve a more complicated one.

*Sometimes constants (like $\log_23$) don't look like constants right away, so you have to keep an eye out for them.

*Converting logs from one base to another just involves multiplying them by a constant factor, which you can easily find with the change of base formula (which you called the base transformation rule).

*When doing asymptotic analysis (big O notation), constant factors go away.


One consequence of the last two points that can also be good to remember is that if I tell you about the asymptotic behavior of some function (or about some algorithm's runtime, or whatever), and it involves a log, you don't have to bother asking me what the base of that log is. You can just convert it to any base you want, and the constant factor from the transformation goes away instantly because we're doing big O.
