# Amortized Analysis of Algorithms

I am currently reading amortized analysis. I am not able to fully understand how it is different from normal analysis we perform to calculate average or worst case behaviour of algorithms. Can someone explain it with an example of sorting or something ?

-
The Wikipedia article on dynamic arrays has a good example of amortized analysis: appending to such an array takes O(n) time in the worst case, but when performing many appends in sequence, the average (amortized) cost of each append becomes O(1). –  larsmans Dec 22 '12 at 12:59
My my answer on programmers.SE might help. –  phant0m Dec 22 '12 at 14:58

Amortized analysis gives the average performance (over time) of each operation in the worst case.

In a sequence of operations the worst case does not occur often in each operation - some operations may be cheap, some may be expensive Therefore, a traditional worst-case per operation analysis can give overly pessimistic bound. For example, in a dynamic array only some inserts take a linear time, though others - a constant time.

When different inserts take different times, how can we accurately calculate the total time? The amortized approach is going to assign an "artificial cost" to each operation in the sequence, called the amortized cost of an operation. It requires that the total real cost of the sequence should be bounded by the total of the amortized costs of all the operations.

Note, there is sometimes flexibility in the assignment of amortized costs. Three methods are used in amortized analysis

1. Aggregate Method (or brute force)
2. Accounting Method (or the banker's method)
3. Potential Method (or the physicist's method)

For instance assume we’re sorting an array in which all the keys are distinct (since this is the slowest case, and takes the same amount of time as when they are not, if we don’t do anything special with keys that equal the pivot).

Quicksort chooses a random pivot. The pivot is equally likely to be the smallest key, the second smallest, the third smallest, ..., or the largest. For each key, the probability is 1/n. Let T(n) be a random variable equal to the running time of quicksort on n distinct keys. Suppose quicksort picks the ith smallest key as the pivot. Then we run quicksort recursively on a list of length i − 1 and on a list of length n − i. It takes O(n) time to partition and concatenate the lists–let’s say at most n dollars–so the running time is

Here i is a random variable that can be any number from 1 (pivot is the smallest key) to n (pivot is largest key), each chosen with probability 1/n, so

This equation is called a recurrence. The base cases for the recurrence are T(0) = 1 and T(1) = 1. This means that sorting a list of length zero or one takes at most one dollar (unit of time).

So when you solve:

The expression 1 + 8j log_2 j might be an overestimate, but it doesn’t matter. The important point is that this proves that E[T(n)] is in O(n log n). In other words, the expected running time of quicksort is in O(n log n).

Also there’s a subtle but important diﬀerence between amortized running time and expected running time. Quicksort with random pivots takes O(n log n) expected running time, but its worst-case running time is in Θ(n^2). This means that there is a small possibility that quicksort will cost (n^2) dollars, but the probability that this will happen approaches zero as n grows large.

Quicksort O(n log n) expected time
Quickselect Θ(n) expected time

For a numeric example:

The Comparison Based Sorting Lower Bound is:

-
Thanks for responding. Your answer was useful. You have given a solution to average case analysis of quicksort. What my doubt was if amortized analysis could be applied here ? If yes, how ? If no, why not ? –  Neeraj Gangwar Dec 23 '12 at 15:48
When the average per operation is all we care about (i.e., sum over all operations), amortized is perfectly fine (This is the usual situation) • If we need every operation to finish quickly (e.g., in a concurrent setting), amortized bounds are too weak • While amortized analysis is about averages, we are averaging cost-per-operation on worst-case input – Contrast: Average-case analysis is about averages across possible inputs. Example: if all initial permutations of an array are equally likely, then quicksort is O(n log n) on average even though on some inputs it is O(n^2)). –  cMinor Dec 23 '12 at 16:25

average - a probabilistic analysis, the average is in relation to all of the possible inputs, it is an estimate of the likely run time of the algorithm.

amortized - non probabilistic analysis, calculated in relation to a batch of calls to the algorithm.

example - dynamic sized stack:

say we define a stack of some size, and whenever we use up the space, we allocate twice the old size, and copy the elements into the new location.

overall our costs are:

• O(1) per insertion \ deletion

• O(n) per insertion ( allocation and copying ) when the stack is full

so now we ask, how much time would n insertions take?

one might say O(n^2), however we don't pay O(n) for every insertion. so we are being pessimistic, the correct answer is O(n) time for n insertions, lets see why:

ignoring copying we would pay O(n) per n insertions.

now, we do a full copy only when the stack has these number of elements:

1,2,4,8,...,n/2,n

for each of these sizes we do a copy and alloc, so to sum the cost we get:

const*(1+2+4+8+...+n/4+n/2+n) = const*(n+n/2+n/4+...+8+4+2+1) <= const*n(1+1/2+1/4+1/8+...)

where (1+1/2+1/4+1/8+...) = 2

so we pay O(n) for all of the copying + O(n) for the actual n insertions

O(n) worst case for n operation -> O(1) amortized per one operation.

-
wow, really good explanation. –  Julian Jan 2 at 1:36
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}