To 'amortize' means to pay off over time.

Consider a sequence  of operations 
e.g.  is ins, del, or find in a BST.
 

If T(  )  O( f( n ) )
Then   O( M f( n ) )

But is this the tightest bound?

A FIFO queue supportsEnqueue( k )andk  Dequeue,
implemented with two stacks :

example

Enqueue order : 1, 2, 3, 4, 5Dequeue order : 1, 2, 3, 4, 5

Note that -
T( Enq )  O( 1 )T( Deq )  O( n ), for n item in the queue

Let  , 

What is T(  )?Clearly, O(  )

Intuition

- Each element is pushed once, transferred once, and popped once.
- So . . . T(  ) is proportional to the number of elements that pass through the queue.
- So . . . T(  )  O( M )

Let  be a sequence of operations.

Define the amortized time complexity,  , of operation  to be any function that satisfies

   

The Amortization Property

is usually chosen as the 'smallest' function satisfying this property.

Intuition

For any prefix of the sequence, the sum of the amortized costs is an upper bound on the true cost.

Intuition

is the "average cost" of  in the context of the set 

Since each element is pushed, transferred, and popped, we will "charge" each element for 3 time units when it is enqueued. Each time unit pays for one of push, transfer, or pop.

Then  ( Enq ) = 3. Since Dequeue uses only transfer and pop, which have already been 'charged for',  ( Deq ) = 0. Note that the functions, and their costs, are arbitrary and specific to this example.

Do these amortized times satisfy the
amortization property?

Yes!

Proof by Induction

Suppose it's true for k-1 operations : 

If  = Enq, then -

 

 

 

If  = Deq, then let -

e be the number of Enq in  ,
s be the size of S,
t be the size of T. Then -

  ( # push + # xfer + # pop ) + T(  )

  ( e + ( e - s ) + ( e - s - t ) ) + T(  )

  ( 3e - 2s - t ) + ( 1 + s )

  3e + 1 - ( s + t )

  3esince s + t  1 ( i.e. queue not empty )

 

  

Therefore, if we choose
   

then we've proven that
 

and "the sum of the amortized costs is an upper bound on the actual cost."

 
  O( M )
which is a better (tighter) bound than our earlier O(  )

But this, you may agree, is cumbersome. Here's an easier way . . .

Let each piece of data 'store' some (virtual) time credits. Each time credit 'pays for' a bounded-time operation on the piece of data. Operations are not charged if they use existing credits.

   

Does this satisfy the property?

 

 

 

i.e. We can't use credits that we've not stored!

- Store two credits on an item when enqueing it.
- Use one when transferring.
- Use one when popping.

=1 + 2 + 0=3

( suppose  transfers s items )

= ( s + 1 ) + 0 - ( s + 1 )where 's' : xfer and '1' : pop

= 0

Is  ?

Yes, since there are always 2 credits on items in S and 1 credit on items in T.