As far as big-Oh notation is concerned, the base of the logarithms doesn't make any real difference, because of this important property, called Change of Base
.
According to this property, changing the base of the logarithm, in terms of big-oh notation, only affects the complexity by a constant factor.
What you should use as a general rule... well, it depends.
Mergesort halves the array, so you should think of it as a base-2 logarithm.
The complexity of algorithms dealing with binary trees made out of n
elements, should use base-2 logarithms, but if dealing with ternary trees made out of n
elements it should be base-3 logarithms.
It's all a matter of counting correctly.
So the only general rule is the change of base property.