POTENTIAL METHOD[CLR 18.3] 

---

Store credit, or 'potential', in the data structure as a whole, not on individual pieces of data.

Let  be the data structure after the  operation.

is the "potential energy" ( "bank balance" in credits, for example ) of  .

Let -

  i.e. actual cost + change in potential

Does this satisfy the Amortization Property?

 

 

  if 

The potential,  , must always be at least as large as the initial potential,  .

Usually,  .

 

should be large before an expensive operation and much smaller afterward!

 

... so that  is comprised of -
large positive cost + very negative change of potential = a small result.

What to choose?

Let  be the number of elements in S. Suppose S has s elements.
Then -

  1 + ( s + 1 ) - ( s )

  2

Suppose S has s elements and Dequeue causes x of them to be transferred to T.
Then -

  ( pop + transfer ) + ( after ) - ( before )

  ( 1 + x ) + ( s - x ) - ( s )

  1

Is  always?

Yes, since  and  .
However, you must always check this condition!

By the amortization property -

 

 

sequence of M Enqueue and Dequeue operations takes at most 2M steps.