6.2.2 Binomial Amortized Analysis

Amortized Analysis of Merge

• To merge two binomial queues, an operation similar to addition of binary integers is performed:

  At any stage, we may have zero, one, two, or three B_ktrees, depending on whether or not the two priority queues contain a B_k tree and whether or not a B_k tree is carried over from the previous step.

  • if there is zero or more B_k tree, it is placed as a tree in the resulting binomial queue.
  • If there are two, they are merged into a B_{k + 1} tree and carried over
  • If there are three, one is retained and other two merged.

Result 1:

• A binomial queue of n elements can be built by n successive insertions in 0(n) time.

• Brute force Analysis
  Define the cost of each insertions to be
  • 1time unit + an extra unit for each linking step
    Thus the total will be n units plus the total number of linking steps.
  • The 1st, 3rd, ... and each odd-numbered step requires no linking steps since there is no B₀ present.
  • A quarter of the insertions require only one linking step: 2nd, 6th, 10, ...
  • One eighth of insertions require two linking steps.

  We could do all this and bound the number of linking steps by n.

  The above analysis will not help when we try to analyze a sequence of operations that include more than just insertions.

• Amortized Analysis

  Consider the result of an insertion.

  • If there is no B₀ tree, then the insertion costs one time unit. The result of insertion is that there is now a B₀ tree and the forest has one more tree.
  • If there is a B₀ tree but not B₁ tree, then insertion costs 2 time units. The new forest will have a B₁ tree but not a B₀ tree. Thus number of trees in the forest is unchanged.
  • An insertion that costs 3 time units will create a B₂ tree but destroy a B₀ and B₁, yielding one less tree in the forest.
  • In general, an insertion that costs c units results in a net increase of 2 - c trees. Since
    • a B_{c - 1} tree is created
    • all B_i trees, 0 $\leq$ i $\leq$ c - 1 are removed.
    Thus expensive insertions remove trees and cheap insertions create trees.

    Let	ti =	$$\mbox{cost of $i^{th}$\space insertion}$$
    	ci =	$$\mbox{no. of trees in forest after $i^{th}$ insertion}$$

    We have

    c0 =	0
    ti + (ci - ci - 1) =	2

Result 2:

• The amortized running times of Insert, Delete-min, and Merge are 0(1), 0(log n), and 0(log n) respectively.

  Potential function = # of trees in the queue

  To prove this result we choose:

• Insertion

  ti	=	$$\mbox{actual cost of $i^{th}$\space insertion}$$
  ci	=	$$\mbox{no. of trees in forest after $i^{th}$ }$$
  ai	=	ti + (ci - ci - 1)
  ai	=	2  $$\forall$$ i
  $$\sum_{i=1}^{n}$$ti	=	$$\sum_{i=1}^{n}$$ai - (cn - c0)
  	=	2n - (cn - c0)

  As long as (c_n - c₀) is positive, we are done.

  In any case (c_n - c₀) is bounded by log n if we start with an empty tree.

• Merge:

  Assume that the two queues to be merged have n₁ and n₂nodes with T₁ and T₂ trees. Let n = n₁+ n₂. Actual time to perform merge is given by:

  ti	= 0(logn1 + logn2)
  	= 0(max(logn1, logn2)
  	= 0(log n)

  (c_i - c_{i - 1}) is at most (log n) since there can be at most (log n) trees after merge.

• Deletemin:
  The analysis here follows the same argument as for merge.