next up previous contents index CD CD Algorithms
Next: Modeling the Problem Up: Introduction to Algorithms Previous: Growth Rates


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 tex2html_wrap_inline23637 is equivalent to saying that tex2html_wrap_inline23639 . 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 tex2html_wrap_inline23641 time, take it and run. As shown by Figure gif, this will be blindingly fast even on very large problem instances.  

Binary search is an example of an algorithm that takes tex2html_wrap_inline23643 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 tex2html_wrap_inline23647 . 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 gif 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 gif 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:

next up previous contents index CD CD Algorithms
Next: Modeling the Problem Up: Introduction to Algorithms Previous: Growth Rates

Mon Jun 2 23:33:50 EDT 1997