amortized analysis in this we will analyze the running times for several of the advanced data structures that have been presented in and in particularwe will consider the worstcase running time for any sequence of operations this contrasts with the more typical analysisin which worst-case bound is given for any single operation as an examplewe have seen that avl trees support the standard tree operations in (log nworst-case time per operation avl trees are somewhat complicated to implementnot only because there are host of casesbut also because height balance information must be maintained and updated correctly the reason that avl trees are used is that sequence of (noperations on an unbalanced search tree could require ( timewhich would be expensive for search treesthe (nworst-case running time of an operation is not the real problem the major problem is that this could happen repeatedly splay trees offer pleasant alternative although any operation can still require (ntimethis degenerate behavior cannot occur repeatedlyand we can prove that any sequence of operations takes ( log nworst-case time (totalthusin the long run this data structure behaves as though each operation takes (log nwe call this an amortized time bound amortized bounds are weaker than the corresponding worst-case boundsbecause there is no guarantee for any single operation since this is generally not importantwe are willing to sacrifice the bound on single operationif we can retain the same bound for the sequence of operations and at the same time simplify the data structure amortized bounds are stronger than the equivalent average-case bound for instancebinary search trees have (log naverage time per operationbut it is still possible for sequence of operations to take (mntime because deriving an amortized bound requires us to look at an entire sequence of operations instead of just onewe expect that the analysis will be more tricky we will see that this expectation is generally realized in this we will analyze the binomial queue operations analyze skew heaps introduce and analyze the fibonacci heap analyze splay trees