Amortized Analysis

AMORTIZED ANALYSIS

10/23/08

KIRAN DEEP KAUR 3RD YEAR COMPUTER SCIENCE 1 AND ENGG.

Introduction This discussion is a useful form of analysis, called amortized analysis, for problems in which one must perform a series of operations, and our goal is to analyze the time per operation. We also introduce the notion of a potential function which can be a useful aid to performing this type 10/23/08

2

Definition The amortized cost of n operations is the total cost of the operations divided by n. No involvement of probability Provide average performance on a sequence of operations, even some operation is expensive.

Often the amortized cost of an operation is less than its worst case.

10/23/08

3

amortized cost and average cost To do averages we need to use probability. For amortized analysis no such assumptions are needed. We compute the “average” cost per operation for any mix of n operations. 10/23/08

4

Three Methods for Amortized Analysis Aggregate analysis Accounting method Potential method

10/23/08

5

Aggregate analysis The total amount of time needed for the n operation is added and divided by n. In worst case the average cost or amortized cost, per operation is therefore T(n)/n. This amortized cost applies to each operation,even when there are several types of operations in the sequence. 10/23/08

6

EXAMPLE

10/23/08

7

Aggregate Method Example A stack with 3 operations push, pop and multipop. multipop (S,k)

while not empty(S) and k!=0 do pop(S); k=k-1; end while Where k is the #objects to be removed from top . 10/23/08

8

push and pop runs in O(1) times, let us consider the cost to be1 . Total cost of multipop operation is min(s,k) and the actual running time is a linear function of this cost. Assume a sequence of n push, pop and multipop operations. Does not provide a separate cost for each type of operation.

10/23/08

9

Description of cost assigned

The number of pushes is at most n Each object can be popped only once for each time it is pushed. So the total number of times pop can be called (directly or from multipop) is bound by the number of pushes ≤ n. The total cost of sequence of n Push and Pop operation is therefore O(n). The worst case time of multipop operation in the sequence is O(n). The amortized cost of each operation which is the average cost per operation is O(n)/n=O(1). 10/23/08

10

Stack Example: Aggregate Method

Operation

Stack

Stack a b a c b a

pop c

a b a c b a b a

pop b

a

Start push a push b push c

multipop (s,3)

pop a 6 Operation: 6 Moves 10/23/08

4 Operation: 6 Moves 11

EXAMPLE-2

10/23/08

12

Increasing a binary counter Binary counter of length k, A[0..k-1] of bit array. INCREMENT(A) i0 while i
10/23/08

13

Analysis of INCREMENT(A) A single execution of INCREMENT takes O(k) in the worst case (when A contains all 1s) So a sequence of n executions takes O(nk) in worst case (suppose initial counter is 0). This bound is correct, but not tight.

The tight bound is O(n) for n executions. 10/23/08

14

Amortized (Aggregate) Analysis of INCREMENT(A) Observation:

The running time determined by #flips but not all bits flip each time INCREMENT is called.

10/23/08

15

A[0] flips every time, total n times. A[1] flips every other time, n/2 times. …. A[2] flips every forth time, n/4 times. for i=0,1,…,k-1, A[i] flips n/2i times.

Thus total #flips is ∑i=0k-1 n/2i < n∑i=0∞ 1/2i =2n.

10/23/08

16

Amortized Analysis of INCREMENT(A) Thus the worst case running time is O(n) for a sequence of n INCREMENTs. The amortized cost per operation is O(1).

10/23/08

17

Accounting method Idea: Assign differing charges to different operations. The amount of the charge is called amortized cost. amortized cost is more or less than actual cost. When amortized cost > actual cost, the difference is saved in specific objects as credits. The credits can be used by later operations whose amortized cost < actual cost.

As a comparison, in aggregate analysis,18

10/23/08

Accounting Method (cont.) Conditions: suppose actual cost is ci for the ith operation in the sequence, and amortized cost is ci', ∑i=1n ci' ≥∑i=1n ci should hold. since we want to show the average cost per operation is small using amortized cost, we need the total amortized cost is an upper bound of total actual cost. holds for all sequences of operations. Total credits is ∑i=1n ci' - ∑i=1n ci , which should be nonnegative, Moreover, ∑i=1t ci' - ∑i=1t ci ≥0 for any t>0.

10/23/08

19

EXAMPLE

10/23/08

20

Operations Actual costs: PUSH :1, POP :1, MULTIPOP: min(s,k). Let assign the following amortized costs: PUSH:2, POP: 0, MULTIPOP: 0. Similar to a stack of plates in a cafeteria. Suppose $1 represents a unit cost. When pushing a plate, use one dollar to pay the actual cost of the push and leave one dollar on the plate as credit. Whenever POPing a plate, the one dollar on the plate is used to pay the actual cost of the POP. (same for MULTIPOP). By charging PUSH a little more, do not charge POP or MULTIPOP. 10/23/08

21

The total amortized cost for n PUSH, POP, MULTIPOP is O(n), thus O(1) for average amortized cost for each operation.

Conditions hold: total amortized cost ≥total actual cost, and amount of credits never becomes negative.

10/23/08

22

EXAMPLE-2

10/23/08

23

Accounting method: binary counter Let $1 represent each unit of cost (i.e., the flip of one bit). Charge an amortized cost of $2 to set a bit to 1. Whenever a bit is set, use $1 to pay the actual cost, and store another $1 on the bit as credit. When a bit is reset, the stored $1 pays the cost. At most one bit is set in each operation, so the amortized cost of an operation is at most $2. Thus, total amortized cost of n operations is O(n), and average is O(1). 10/23/08

24

The Potential Method Initial data structure D0, n operations, resulting in D0, D1,…, Dn with costs c1, c2,…, cn. A potential function Φ: {Di}  R (real numbers Φ(Di)). Φ(Di) is called the potential of Di. Amortized cost ci' of the ith operation is: ci' = ci + Φ(Di) - Φ(Di-1). (actual cost + potential change)

∑i=1n ci' = ∑i=1n (ci + Φ(Di) - Φ(Di-1)) . 10/23/08

25

The Potential Method (cont.) If Φ(Dn) ≥ Φ(D0), then total amortized cost is an upper bound of total actual cost. But we do not know how many operations, so Φ(Di) ≥ Φ(D0) is required for any i. It is convenient to define Φ(D0)=0,and so Φ(Di) ≥0, for all i. If the potential change is positive (i.e., Φ(Di) Φ(Di-1)>0), then ci' is an overcharge (so store the increase as potential), otherwise, undercharge (discharge the potential to pay the actual cost).

10/23/08

26

EXAMPLE

10/23/08

27

Potential method: stack operation Potential for a stack is the number of objects in the stack. So Φ(D0)=0, and Φ(Di) ≥0 Amortized cost of stack operations: PUSH: Potential change: Φ(Di)- Φ(Di-1) =(s+1)-s =1. Amortized cost: ci' = ci + Φ(Di) - Φ(Di-1) =1+1=2. POP: Potential change: Φ(Di)- Φ(Di-1) =(s-1) –s= -1. Amortized cost: ci' = ci + Φ(Di) - Φ(Di-1)=1+(-1)=0. MULTIPOP(S,k): k'=min(s,k) Potential change: Φ(Di)- Φ(Di-1) = –k'. Amortized cost: ci' = ci + Φ(Di) - Φ(Di-1)=k'+(k')=0.

10/23/08

28

So amortized cost of each operation is O(1), and total amortized cost of n operations is O(n).

Since we have already urged that Φ(Dn) ≥ Φ(D0), the total amortized cost is an upper bound on the actual cost, the worst case cost of n operations is O(n).

10/23/08

29

EXAMPLE-2

10/23/08

30

Potential method: binary counter Define the potential of the counter after the ith INCREMENT is Φ(Di) =bi, the number of 1’s. clearly, Φ(Di)≥0. Let us compute amortized cost of an operation

10/23/08

Suppose the ith operation resets ti bits. Actual cost ci of the operation is at most ti +1. If bi=0, then the ith operation resets all k bits, so bi-1=ti=k. If bi>0, then bi=bi-1-ti+1 In either case, bi≤bi-1-ti+1. So potential change is Φ(Di) - Φ(Di-1) ≤bi-1-ti+1-bi1=1-ti. So amortized cost is: ci' = ci + Φ(Di) - Φ(Di-1) ≤ ti +1+1-ti=2. 31

The total amortized cost of n operations is O(n). Thus worst case cost is O(n).

10/23/08

32

Applications of amortized analysis Vectors/ tables Disjoint sets Priority queues Binomial heaps (insert O(1) amortized cost, O(lgn) worst case) Hashing Reducing the load factor by doubling Universal hashing 10/23/08

33

SUMMARY In Amortized Analysis we examine the total time sequence of operations. This analysis determine the average time of without the use of probability. In aggregate analysis we have to compute worst case running time T(n) for sequence of n operations. In accounting method we assign different charge to different operations. Potential method stores prepayment as a “potential energy” or just “potential” to pay for future operations. 10/23/08

34

10/23/08

35