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.