Aggregate analysis We show that for all n, a sequence of n operation takes worst-case time T(n)in total Hence, the average cost, or amortized cost, per operation is T(n)/n
Aggregate analysis y We show that for all n, a sequence of n operation takes worst-case time T( n ) in total. y Hence, the average cost, or amortized cost, per operation is T( n)/ n
MULTIPOP (aggregate method Each object can be popped at most once for each time it is pushed. Therefore, the number of times that POP can be called on a nonempty stack including calls within MULtIPOP, is at most the number of push operations which is at most n Any sequence of n Push, POP, and MULtIPOP operations takes a total of o(n) time. The average cost of an operation is T(n)/n=O(1)
MULTIPOP (aggregate method) y Each object can be popped at most once for each time it is pushed. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP, is at most the number of PUSH operations, which is at most n. y Any sequence of n PUSH, POP, and MULTIPOP operations takes a total of O ( n ) time. The average cost of an operation is T( n)/ n = O(1 )
8-bit binary counter Counter Total Value p cost 000000000 00000001 200000010 300000011 400000100 013478 00000101 5678 00000110 10 00000111 00001000 5
8-bit binary counter 0000000 0 000000 0 1 0000001 0 00000 0 1 1 0000010 0 000001 0 1 0000011 0 0000 0 1 1 1 0000100 0 0 1 2 3 4 5 6 7 8 A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] 0 1 3 4 7 8 10 11 15 Counter Value Total cost
Incrementing a binary counter An array A[0..k-1] of bit, where length[a-k, as the counter i=0 A[i]·2 INCREMENT(A 1.i←0 2. while i length and ai= l 3.doA[←0 4. 5. if i length[A] then Ai
Incrementing a binary counter An array A[0 … k − 1] of bit, where length [A] = k, as the counter. 1 0 [] 2 k i i x A i − = = ∑ ⋅ INCREMENT (A ) 1. i ← 0 2. while i < length [A] and A [ i] = 1 3. do A [ i ] ← 0 4. i = i + 1 5. if i < length [A] 6. then A [ i ] ← 1
Binary counter(aggregate method For i=0,1., LIgnl, bit A(i] flips n/2 times in a sequence of n INCREMENT operation on an initially zero counter The total number of flips in the sequence is thus n 2n O(n) The amortized cost per operation is O(n)n=O(1)
Binary counter (aggregate method) For i = 0, 1 …, , bit A [ i ] flips times in a sequence of n INCREMENT operation on an initially zero counter. ⎢⎣lg n⎥⎦ / 2i ⎢n ⎥ ⎣ ⎦ The total number of flips in the sequence is thus lg 0 0 1 2 2 n i i i i n n ⎢ ⎥ ⎣ ⎦ ∞ = = ⎢ ⎥ < ⎢ ⎥ ⎣ ⎦ ∑ ∑ = 2 n = O ( n ) The amortized cost per operation is O ( n)/ n = O(1)