When working with Mergesort, quicksort etc, is O(n log n) base 2, or base 10?

Question

I'm a little confused about big O notations.

Let's say I'm working with an array of 16 elements and trying to do a QuickSort.

A QuickSort's Average case is O(n log n) and its worst case is O(n^2)

I assumed it would be log base 2 since we're working with computers (binary). But I've also heard you could use base 10 and get the same complexity.

I figured it would be 16*log2*16 == 16 * 4 = 64 comparisons at O(n log n).

At O(n^2) == 16^2 == 256 comparisons at its worst case.

Do I have the right idea? And as a general rule, should I be using base 10 or base 2?

Answer 1

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.