Answer to Question lec33C-4

Doubling the size of the queue means that an insertion step that needs to call enlarge takes more than a fixed amount of time. Its time is proportional to the number of values in the queue when the operation is performed. So some operations are expensive.

However, we can argue that expensive operations are so infrequent that the total time of performing n operations is O(n). So the average time per operation is O(1). Moreover, the average is over the n operations, and has nothing to do with the order in which operations are performed. The average time per operation is O(1) regardless of which operations are done, or in which order they are done. We say that the queue operations take O(1) amortized time.

An argument for O(1) amortized time is not very difficult. Suppose that we charge one dollar for each operation except for an insertion, since those operations always take a constant amount of time. We also charge one dollar for an insertion that does not need to call enlarge. If an insertion calls enlarge, and it is performed when there are m things in the queue, then we charge m dollars for it. Our goal is to show that n operations cost O(n) dollars.

Each time a one-dollar insertion is done, let's put two dollars into a piggy bank. That makes the one-dollar insertion cost us three dollars, counting the extra dollars put into savings. That is okay, since the cost of that operation is still a constant number of dollars.

A little thought shows that, any time an m-dollar insertion is done, there must have been at least m/2 one-dollar insertions done before that, and that there must be at least m dollars in the piggy bank. For example, suppose that we have just enlarged the array to from size 100 to size 200. Then 100 of the slots are empty. It will take 100 cheap insertions before the next enlargement is done. Those cheap insertions will lead to $200 being put into the piggy bank. Now, when the $200 enlargement is needed, we pay for it with the money in the piggy bank. So our direct cost for that enlargment is 0. (Remember that we already charged for the deposits into the piggy bank.)

Really, the piggy bank is just a way of smoothing out the charges, so it is nothing but a convenient way of counting the total cost, which averages to a contant per operation.