in we described rehashingwhen table becomes more than half fulla new table twice as large is constructedand the entire old table is rehashed give formal amortized analysiswith potential functionto show that the amortized cost of an insertion is still ( what is the maximum depth of fibonacci heapa deque with heap order is data structure consisting of list of items on which the following operations are possiblepush( )insert item on the front end of the deque pop()remove the front item from the deque and return it inject( )insert item on the rear end of the deque eject()remove the rear item from the deque and return it findmin()return the smallest item from the deque (breaking ties arbitrarilya describe how to support these operations in constant amortized time per operation  describe how to support these operations in constant worst-case time per operation show that the binomial queues actually support merging in ( amortized time define the potential of binomial queue to be the number of trees plus the rank of the largest tree suppose that in an attempt to save timewe splay on every second tree operation does the amortized cost remain logarithmicusing the potential function in the proof of the splay tree boundwhat is the maximum and minimum potential of splay treeby how much can the potential function decrease in one splayby how much can the potential function increase in one splayyou may give big-oh answers as result of splaymost of the nodes on the access path are moved halfway towards the rootwhile couple of nodes on the path move down one level this suggests using the sum over all nodes of the logarithm of each node' depth as potential function what is the maximum value of the potential functionb what is the minimum value of the potential functionc the difference in the answers to parts (aand (bgives some indication that this potential function isn' too good show that splaying operation could increase the potential by (nlog references an excellent survey of amortized analysis is provided in [ most of the references below duplicate citations in earlier we cite them again for convenience and completeness binomial queues were first described in [ and analyzed in [ solutions to exercises and appear in [ fibonacci heaps are described in [ exercise (ashows that splay trees are optimalto within constant