Accounting method We denote the actual cost of the ith operation by c and the amortized cost of the ith operation by c we require hv?
Accounting method y We denote the actual cost of the ith operation by ci and the amortized cost of the ith operation by , we require l i c l 1 1 n n i i i i c c = = ∑ ≥ ∑ Why?
Binary counter(accounting method) Amortized costs Set a bit to 1 2 flip the bit back too 0
Binary counter (accounting method) Set a bit to 1 Flip the bit back to 0 Amortized costs 2, 0
Potential method For each i=1.2... n we let c: be the actual cost of the ith operation and d be the data structure that results after applying the ith operation to data structure Di-1 a potential function p maps each data structure D to a real number (D), which is the potential associated with data structure D a amortized cost c: of ith operation with respect to potential function is g defined b c1=c+Φ(D)-Φ(D=1
Potential method y For each i = 1, 2, …, n, we let ci be the actual cost of the ith operation and Di be the data structure that results after applying the ith operation to data structure Di− 1. y A potential function Φ maps each data structure Di to a real number Φ (Di ), which is the potential associated with data structure Di . y A amortized cost of ith operation with respect to potential function is Φ defined by l 1 ( ) ( ). ii i i cc D D = +Φ −Φ − l i c