Logarithm is an anagram of algorithm, but that's not why
the wily algorist needs to know what logarithms are and where they come from.
You've seen the button on your calculator but have likely forgotten
why it is there.
A logarithm is simply an inverse exponential function.
Saying 
is equivalent to saying that 
.
Exponential functions
are functions that grow at a distressingly fast rate,
as anyone who has ever tried to pay off a mortgage or bank loan understands.
Thus inverse exponential functions, i.e. logarithms, grow refreshingly slowly.
If you have an algorithm that runs in 
time, take it and run.
As shown by Figure 
,
this will be blindingly
fast even on very large problem instances.
Binary search is an example of an algorithm that takes time.
In a telephone book
with n names, you start by comparing the name that you are looking for
with the middle, or (n/2)nd name, say Monroe, Marilyn.
Regardless of whether you are looking someone before this middle name
(Dean, James) or after it (Presley, Elvis), after only
one such comparison you can forever disregard one half of all the names
in the book.
The number of steps the algorithm takes equals the number of times we
can halve n before only one name is left.
By definition, this is exactly 
.
Thus twenty comparisons suffice to find any name in the million-name Manhattan
phone book!
The power of binary search and logarithms is one of the most
fundamental ideas in the analysis of algorithms.
This power becomes apparent if we
could imagine living in a world with only unsorted telephone books.
Figure is another example of logarithms in action.
This table appears in the Federal Sentencing Guidelines, used by courts
throughout the United States. These guidelines are an attempt to standardize criminal
sentences, so that a felon convicted of
a crime before one judge receives the same sentence as they would before
a different judge.
To accomplish this, the judges have prepared an intricate point function
to score
the depravity of each crime and map it to time-to-serve.
Figure:
The Federal Sentencing Guidelines for Fraud
Figure gives
the actual point function for fraud,
a table mapping dollars stolen to points.
Notice that the punishment increases by one level each time
the amount of money stolen roughly doubles.
That means that the level of punishment (which maps roughly linearly to
the amount of time served) grows logarithmically with the amount of money
stolen.
Think for a moment about the consequences of this.
Michael Milken sure did.
It means that the total sentence grows extremely slowly with the amount
of money you steal.
Knocking off five liquor stores for $10,000 each will get you far more
time than embezzling $100,000 once.
The corresponding benefit of stealing really large amounts of money is
even greater.
The moral of logarithmic growth is clear:
``If you are gonna do the crime, make it worth the time!''
Two mathematical properties of logarithms are important to understand:
,
, and 
.
A big change in the base of the logarithm produces relatively little
difference in the value of the log.
This is a consequence of the formula for changing the base of the logarithm:
Changing the base of the log from a to c involves multiplying or
dividing by 
.
This will be lost to the big Oh notation whenever
a and c are constants, as is typical.
Thus we are usually justified in ignoring the base of the logarithm
when analyzing algorithms.
When performing binary search in a telephone book,
how important is it that each query split the book exactly in half?
Not much.
Suppose we did such a sloppy job of picking our queries such that
each time we split the book 1/3 to 2/3 instead of 1/2 to 1/2.
For the Manhattan telephone book, we now use 
queries in the worst case, not
a significant change from 
.
The power of binary search comes from its logarithmic complexity,
not the base of the log.
.
This follows because
The power of binary search on a wide range of problems is a consequence
of this observation.
For example, note that doing a binary search on a sorted array of 
things
requires only twice as many comparisons as a binary search on n things.
Logarithms efficiently cut any function down to size.