amortized analysis minimum and splitting the original binomial queue into two binomial queueswhich are then merged less terse explanation of these operations is given in we consider very simple problem first suppose we want to build binomial queue of elements we know that building binary heap of elements can be done in ( )so we expect similar bound for binomial queues claim binomial queue of elements can be built by successive insertions in (ntime the claimif truewould give an extremely simple algorithm since the worst-case time for each insertion is (log )it is not obvious that the claim is true recall that if this algorithm were applied to binary heapsthe running time would be ( log nto prove the claimwe could do direct calculation to measure the running timewe define the cost of each insertion to be one time unit plus an extra unit for each linking step summing this cost over all insertions gives the total running time this total is units plus the total number of linking steps the st rd thand all odd-numbered steps require no linking stepssince there is no present at the time of insertion thushalf the insertions require no linking steps quarter of the insertions require only one linking step ( nd th thand so onan eighth requires twoand so on we could add this all up and bound the number of linking steps by nproving the claim this brute-force calculation will not help when we try to analyze sequence of operations that include more than just insertionsso we will use another approach to prove this result consider the result of an insertion if there is no tree present at the time of the insertionthen the insertion costs total of one unitusing the same accounting as above the result of the insertion is that there is now treeand thus we have added one tree to the forest of binomial trees if there is tree but no treethen the insertion costs two units the new forest will have tree but will no longer have treeso the number of trees in the forest is unchanged an insertion that costs three units will create tree but destroy and treeyielding net loss of one tree in the forest in factit is easy to see thatin generalan insertion that costs units results in net increase of trees in the forestbecause bc- tree is created but all bi trees < are removed thusexpensive insertions remove treeswhile cheap insertions create trees let ci be the cost of the ith insertion let ti be the number of trees after the ith insertion is the number of trees initially then we have the invariant ci (ti ti- we then have ( ( cn- (tn- tn- cn (tn tn- (