Intro to Amortized Analysis

This is the first of series of blog posts I intend to make regarding Data Structures. Hopefully these will be informative for anyone who has stumbled to this site, but more importantly, these posts will form the basis for a textbook I am writing for my graduate data structures class. So without further ado, let me present my first topic.

 

Amortized Analysis

Definition: Amortized – “to pay money that is owed for something (such as a mortgage) by making regular payments over a long period of time” ~ Merriam Webster

Which sounds worse? Paying $30 now or paying $1 a day for the rest of the month? Although they are the same amount of money, many people would rather part with their cash in smaller increments spread over a long period of time. Similarly, when making a large purchase, for example a $2000 laptop, it is common to justify the expense by saying “buy I will use that laptop for the next five years!” Such a statement is unconscious amortization.

In algorithmic analysis, similar justifications help programmers understand the complexity of their programs. If an operation is almost always quick to compute, but once in a while takes a lot longer, is it really right to give it a high Big-O value?

Although there are certainly algorithmic purists reading this shaking their heads, there are two algorithms used every day which are best understood when their costs are amortized: incrementing a binary counter and quick sort.

By incrementing a binary counter, I mean it. If B is a number stored on a computer, what is the complexity of B++? If you guessed O(1) then you would unfortunately be mistaken.

In the following chart, we can see what it looks like to increment a binary counter:


Across the top we can see the binary value represented in base 10. Across the side, for reference, we can see the powers of 2 which correspond to each bit. And across the bottom, we can see the number of flips required to go from the previous to the current column. This should look pretty familiar to anyone who has played with binary for a substantial length of time (most of us). And we can continue this table, of course, as far as we want. I went to 64:


Of course, the pattern continues, and slowly grows every time we need to increment a new bit. Although there is practically no faster operation than B++ (except ++B of course!) it is technically an O(log N) operation.

Does this mean that any algorithm which increments a variable is automatically O(log N)? That doesn’t sound very useful. This is where amortized analysis comes in to make sense of this mess.

 To Be Continued!