Recall the optimal list :

where 

(  is the probability that the next search is for  )

We don't know the probabilities. The structure is a dynamic linked list; upon search for an item, that item is moved to the front of the list. In this way, frequently-sought items will tend to stay near the front.

What is  as compared to  ?

Probabilistic analysis shows that -

- but says nothing about the worst case.

We will show that -

This is a much stronger statement!

Probabilistic analysis tells us what happens on average, not what happens in the worst case. Amortized analysis gives us the worst-case analysis for a sequence of operations.

Potential Method

Let  be the optimal static list.

Let  ( L ) be the number of pairs of elements of L which are in a different order in  ( called 'inversions' ).

 

e.g.	= a b c d  L = a c d b  ( L ) = 2

 

What is the minimum  ( L ) ?

0 when L = 

What is the maximum  ( L )?

When L = reverse(  ), every pair is inversed,
there are 

Let  be L after the  search.
Let  be the  find operation on  .

( Let  be  in an optimal list )

From  to  ,  changes order with each element in A.
's order remains the same for the elements in B.
precedes  in  .

Suppose  :

- the new inversion increases  by 1.

Suppose  :

- the inversion disappears, so  decreases by 1.

Let a be the number of elements  such that j < k.

a	is the number of inversions created.
|A| - a	is the number of inversions removed.

Then -

 

  we are paying 2 for each inversion created.

We want to compare  and  , the time to find  in  .

 (  k is in the  position )

But 'a' is the number of elements  such that j < k,
which is  the number of elements  such that j < k,
which is  k - 1.

So 

But the list has some elements in it before the first 'find'. For the whole sequence :

,

where 
 
 

where  doesn't change as M increases.

So 

and  as  .

This is better than the probabilistic analysis, since it applies to all sequences of finds, not just the average case.