analogies:

1. cost of employee:

while working is salary + contribution to pension

after retire; just from pension.

Here think of working years as the "normal" ones, and the retirement years as the special cases:

Idea is to set the pension contribution high enough to pay for retirement. (Don't look at the state of Illinois for a good model.)

2. What routine deposits do you makle to a bank account being kept for emergencies, so you never overdraw the account in an emergency?

One common situation in programming is to have a normal low actual cost and costs associated with the bank for ocasional larger costs.

The amortized cost is normal basic cost + normal bank deposit. This only makes sense if the bank is never overdrawn in special cases/emergencies.

For our purposes, we do not need to always know the exact bank balance. We only want to prove the amount in the bank will never go negative.

The term accounting cost is used for the bank transactions. Deposits are positive in the usual case and negative in the special cases where we want to offset high actual costs.

Assume the real excess cost of changing array size is the number of elements copied.

We can calculate the cost of the normal bank deposit, call it c, to absorb the extra cost of a push when the array is already full and needs to be doubled in size. For simplicity assume the initial array size is 1, so all the sizes when it needs to be doubled are powers of 2. Thus the special cases only come when n = 2

In the worst case there are no pops, which just relieve the space problems. We will consider the worst case, when there are only pushes.

You could try to figure this out by trial and error. For example, assume the initial array size is 1, and assume it costs 1 for each element copied to a new array, and arbitrarily make the accounting cost c = 1. The columns show the state after the specified action, with n being the number of elements in the stack, and N being the array size. The calculation in the accounting column shows the old balance plus the routine addition of 1, minus the special costs at array doubling/copying time, that comes when the stack grows just beyond a power of 2:

Action n N Accounting/bank balance

0 1 0 (initial state)

Push 1 1 0+1=1

Push 2 2 1+1-1=1

Push 3 4 1+1-2=0

Push 4 4 0+1=1

Push 5 8 1+1-4=-2 oops, accounting cost 1 does not work!

Now let us try to solve this in general, assuming a constant accounting cost for each push. Call it c. The total positive contributions for n pushes are cn. The balance can only go negative after a debit, so only consider n = 2

To avoid debt we need all the deposits so far to be as big as all the debits so far:

cn >= 2

To reduce the number of symbols, use n = 2

cn >= 2

Clearly to keep cn >= 2n - 3, c = 2 is the best value.

This approach works because it is easy to simplify to a final state with one clear worst path to it (after doubling space repeatedly and ending with n = 2

A simpler approach that may provide a usable accounting cost: The balance must always be nonnegative. It starts off nonnegative, and in particular, right after we must make a withdrawal from the amortizing account, it must be nonnegative. We may be able to use an inductive approach where we only look from one action requiring a withdrawal to the next. If we add enough between the withdrawals to sustain the next withdrawal, we are covered.

Induction basis: Starting balance = 0

Induction hypothesis: Through k deductions, the amortizing balance is nonnegative,

Then show the additions to the amortizing balance for the time after the kth deduction through k+1st deduction will be enough to pay for the k+1st deduction. Hence the amortizing balance after the k+1st deduction will be at least as high as after the kth deduction.

Conclude: The amortizing balance will be nonnegative after any number of deductions.

This approach works for the array doubling example above. We make no further assumption about the balance after the previous array expansion, other than it must be nonnegative, and assume the next expansion comes after the array fills up at size N. The last expansion was caused when an array of size N/2 was full, and another element needed to be addeded. That triggered the allocation of an array of length N, receiving N/2+1 elements, and possibly no accounting balance. The expansion from N to N+1 elements will require copying N elements into an array of size 2N, at a real cost of N, and the accounting balance needs to pay for it. Pushes increased the size from N/2+1 to N+1, for a total of N/2 pushes which contribute cN/2 to the accounting balance. It is sufficient if these most recent additions at least pay for the next doubling, which must cover the copying cost N: cN/2 >= N. Again c = 2.

What about adding K to the array size each times it fills up instead of doubling the size? Assume the initial array size is K. What would happen if we try to find the value, c, for accounting costs for each push?

Following the first analysis: the worst case will be pushes up past some multiple of K, say bK, so n = bK+1, b = (n-1)/K. We need cn >= K + 2K + .... + bK = Kb(b+1)/2 = (n-1)((n-1)/K+1)/2, which is Θ(n

This sort of analysis with an extra payment for each "normal" operation, allows a stack or a growable list to be used in any larger algorithm, and always assume that pushes and pops average a constant amount of work.

There are other sophisticated approaches to amortizing (for instance in the proof for the overall time for union-find in Ch 9), but we will not look in detail at any other sort of examples in this course, so we stop here.

Amortizing-1. An obvious shrinking mechanism is the inverse of the growing one: As soon as the stack uses less than half of its space, halve the size of the array. Look at the interaction with the doubling part, and show the worst case behavior of this stack is O(n), not O(1). If you do not see this right away, more systematically consider breaking the problem into four cases, as in the next problem.

Amortizing-2. What if the array only shrinks to half its size when 1/4 of the array is occupied? Is the average here for pushes and pops O(1)? Hints: You can use my simpler approach to accounting, that only looks from one withdrawal ( array size change) to the next. In the case where the array only doubled, there was one clear worse case. Now there are several patterns. Still there are a finite number of situations: grow after growing, shrink after growing, shrink after shrinking, and grow after shrinking. The overall worst case is the worse possibility among these 4. Let c, the regular bank contribution, be a parameter and solve an inequality (4 times). Make clear in your argument the distinction between the symbols for the current size of the array and the current number of elements in it, vs the number of elements at the next or previous array doubling.

On to some dynamic data structures.