Math in computer science: logarithms

In high school you may have seen a definition of logarithm that included multiplication.

  • The logarithm base 10 of 1000 is 3 because 1000 = 10^3 = 10 \times 10 \times 10.
  • The logarithm base 2 of 1024 is 10 because 1024 = 2^{10} = 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2.

We get 1000 by computing the product of three tens. We get 1024 by computing the product of ten twos.

When we ask for the logarithm base ten of a number x we are asking: “To what power must I raise 10 to get x?” or (equivalently) “How many tens must I put in a product to get x?”

When we ask for the logarithm base two of a number x, we are asking: “To what power must I raise 2 to get x?” or (equivalently) “How many twos must I put in a product to get x?”

In the analysis of algorithms, logarithms will show up when we look at some “divide and conquer” algorithms. Why? Let’s define logarithm with a reference to divisions instead of multiplications.

The logarithm base 10 of 1000 is 3 because, starting at 1000, we can get to 1 by dividing 3 times. The first division by 10 gives 100. A second. division by 10 gives 10. And a third division by 10 gives 1.

1000 \rightarrow 100 \rightarrow 10 \rightarrow 1

The logarithm base 2 of 1024 is 10 because, starting at 1024, we can get to 1 by dividing 10 times. The first division by 2 gives 512. Successive divisions give 256, 128, 64, 32, 16, 8, 4, 2, and 1.

1024 \rightarrow 512 \rightarrow 256 \rightarrow 128 \rightarrow 64 \rightarrow 32 \rightarrow 16 \rightarrow 32 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1

The merge sort is a divide and conquer algorithm. It sorts the elements of a list by dividing the list in half, sorting the two halves, and then merging the sorted halves.

How does it sort the halves? It divides the halves in half.

How does it sort the quarters? It divides the quarters in half to produce smaller lists that each have a length equal to one eighth the length of the whole list. This continues until the divisions produce sublists that each contain just one element.

Of course, a list with one element is sorted. The splitting stops there.

The analysis of the merge sort algorithm counts divisions. This count of divisions is a logarithm.