Amortized Analysis? (Worst-case Performance Guarantees)

Question

What is Amortized Analysis? And how can it help me achieve worst-case performance guarantees in my programs?

I was reading that the following techniques can help the programmer achieve Worst-case performance guarantees (i.e. in my own words: guarantee that the running time of a program would not exceed the running time in the worst cast):

• Randomized algorithms (e.g. quicksort algorithm is quadratic in worst case, but randomly ordering the input gives a probabilistic guarantee that its running time is linearithmic )
• Sequences of operations (our analysis must take into account both data and the sequence of operations performed by the client)
• Amortized Analysis (another way to provide a performance guarantee is to amortize the cost, by keeping track of the total cost of all operations, divided by the number of operations. In this setting, we can allow some expensive operations, while keeping the average cost of operations low. In other words, we spread the cost of the few expensive operations, by assigning a portion of it to each of a large number of inexpensive operations)

The author mentioned the use of resizing array data structure for Stack as one example of how to achieve amortized analysis but I still don't understand what amortized analysis is, and how it can actually be implemented (data structure? algorithm?) to achieve worst-cast performance guarantees

Answer 1

You don't implement amortized analysis. It's a technique to get more accurate O bounds.

The essential observation you have to make is, that expensive operations cannot happen at any time.

In the case of an array-backed data structure, the array needs resizing every now and then – when it's full. This is the most expensive operation and takes O(n) time. All other inserts into the array are O(1).

To determine the runtime for inserting n items, you can multiply n with the most expensive operation O(n), which results in an overall runtime behavior of O(n^2).

However, this is inaccurate because resizing cannot happen very often.

When talking about money, you amortize cost, when you pay off your debt with multiple small payments over time.

We can use this model to think about algorithms as well. We simply substitute "time" with "money" to avoid mental mapping.

Once the array is fulled to it's length n, we can double it's size. We need to make the following operations:

• Allocate 2n chunks of memory
• copy n items

If we assume that both allocating memory and copying happen in linear time, this is going to be a very expensive operation. However, we can now use the idea of debt and amortizing it for our analysis. Only, we are going to amortize our debt before we actually make it.
Let's assume, that our balance (of money/time) is back to 0 (i.e. we don't have a debt nor do we have any leftovers) once we have resized the array.

This has the following implication:

• Inserting the next n items will cover the cost of resizing and copying (we have n used slots, and n unused slots`)

We can now think about how much every insert operation needs to pay for:

• The insert
• The cost of allocating one chunk of memory
• the cost of moving it to the newly allocated memory

We have now covered the costs to allocate memory, copy and insert the next n elements. However, we have yet neglected allocating space for the old n elements as well as copying them.

We simply distribute the costs of our old n elements to our new (yet to be inserted) n elements:

• The cost of allocating one chunk of memory
• the cost of moving it to the newly allocated memory

In total, every, every insert operation will cost 5 units. This pays for its own insertion, and the moving and allocating of space for itself and one of the old elements.

Every insert-operation still takes constant amount of time, but the resizing happens for free: We amortized it by spending "more" time on each insertion.

As a result, inserting n elements takes O(n) time.

Other techniques for amortized analysis are explained here.

Answer 2

First of all: It is a technique for analyzing program runtimes, not an implementation technique for algorithms.

The example mentioned in your list is a good one: Appending a single item to array-backed data-structure. For every single append operation the worst-case is having to copy all existing items. That kind of analysis is way too pessimistic, as you don't have to do that if you are using a sane resizing strategy (multiplying the size by some x > 1.0). The analysis then says you have a O(n^2) bound - O(n) per item times n items - while the actual runtime is only O(n).

If you average the resizing cost over all items inserted (most of which don't need resizing) you are doing amortized analysis. The amortized analysis results in a O(n) bound which matches the actual behaviour of the algorithm.