Big O confusion: log2(N) vs log3(N)

Question

Why is O(log₂N) = O(log₃N) ?

I don't understand this. Does big O not mean upper bound of something?

Isn't log₂N bigger than log₃N ? When I graph them, log₂N is above log₃N .

Answer 1

Big O doesn't deal with constant factors, and the difference between Log_x(n) and Log_y(n) is a constant factor.

To put it a little differently, the base of the logarithm basically just modifies the slope of a line/curve on the graph. Big-O isn't concerned with the slope of the curve on the graph, only with the shape of the curve. If you can get one curve to match another by shifting its slope up or down, then as far as Big-O notation cares, they're the same function and the same curve.

To try to put this in perspective, perhaps a drawing of some of the more common curve shapes would be useful:

As noted above, only the shape of a line matters though, not its slope. In the following figure:

...all the lines are straight, so even though their slopes differ radically, they're still all identical as far as big-O cares--they're all just O(N), regardless of the slope. With logarithms, we get roughly the same effect--each line will be curved like the O(log N) line in the previous picture, but changing the base of the logarithm will rotate that curve around the origin so you'll (again) have he same shape of line, but at different slopes (so, again, as far as big-O cares, they're all identical). So, getting to the original question, if we change bases of logarithms, we get curves that look something like this:

Here it may be a little less obvious that all that's happening is a constant change in the slope, but that's exactly the difference here, just like with the straight lines above.

Answer 2

It is because changing base of logarithms is equal to multiplying it by a constant. And big O does not care about constants.

log_a(b) = log_c(b) / log_c(a)

So to get from log2(n) to log3(n) you need to multiply it by 1 / log(3) 2.

In other words log2(n) = log3(n) / log3(2).

log3(2) is a constant and O(cn) = O(n), thus O (log2(n)) = O (log3(n))

Answer 3

There are some good answer here already, so please read them too. To understand why Log2(n) is O(log3(n)) you need to understand two things.

1) What is mean by BigO notation. I suggest reading this: http://en.wikipedia.org/wiki/Big_O_notation If you understnad this,you will know 2n and 16n+5 are both O(N)

2) how logarithms work. the difference between log₂ (N) and log₁₀(N) will be a simple ratio, easily calculated if you want it as per luk32's answer.

Since logs at different bases differ only a by a constant ratio, and Big O is indifferent to minor things like constant multiplying factors, you will often find O(logN) actually omits the base, because the choice of any constant base (eg 2,3,10,e) makes no difference in this context.