amortized analysis the keys to choosing potential function are to guarantee that the minimum potential occurs at the beginning of the algorithmand to have the potential increase for cheap operations and decrease for expensive operations it is important that the excess or saved time be measured by an opposite change in potential unfortunatelythis is sometimes easier said than done exercises when do consecutive insertions into binomial queue take less than time unitssuppose binomial queue of elements is built alternately perform insert and deletemin pairs clearlyeach operation takes (log ntime why does this not contradict the amortized bound of ( for insertionshow that the amortized bound of (log nfor the skew heap operations described in the text cannot be converted to worst-case bound by giving sequence of operations that lead to merge requiring (ntime show how to merge two skew heaps with one top-down pass and reduce the merge cost to ( amortized time extend skew heaps to support the decreasekey operation in (log namortized time implement fibonacci heaps and compare their performance with that of binary heaps when used in dijkstra' algorithm standard implementation of fibonacci heaps requires four links per node (parentchildand two siblingsshow how to reduce the number of linksat the cost of at most constant factor in the running time show that the amortized time of zig-zig splay is at most (rf (xri ( )by changing the potential functionit is possible to prove different bounds for splaying let the weight function (ibe some function assigned to each node in the treeand let (ibe the sum of the weights of all the nodes in the subtree rooted at iincluding itself the special case ( for all nodes corresponds to the function used in the proof of the splaying bound let be the number of nodes in the treeand let be the number of accesses prove the following two theoremsa the total access time is ( ( nlog nb if is the number of times that item is accessedand for all ithen the total access time is mqi log( /qi = show how to implement the merge operation on splay trees so that any sequence of - merges starting from single-element trees takes ( log ntime improve the bound to ( log