In high school you may have seen a definition of logarithm that included multiplication.
- The logarithm base
of
is
because
. - The logarithm base
of
is
because
.
We get
by computing the product of three tens. We get
by computing the product of ten twos.
When we ask for the logarithm base ten of a number
we are asking: “To what power must I raise
to get
?” or (equivalently) “How many tens must I put in a product to get
?”
When we ask for the logarithm base two of a number
, we are asking: “To what power must I raise
to get
?” or (equivalently) “How many twos must I put in a product to get
?”
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
of
is
because, starting at
, we can get to
by dividing
times. The first division by
gives
. A second. division by
gives
. And a third division by
gives
.
![]()
The logarithm base
of
is
because, starting at
, we can get to
by dividing
times. The first division by
gives
. Successive divisions give
and
.
![]()
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.