15-451 Algorithms: Lecture 2/17/00 Announcements: - Info on distribution of homework #1 scores posted shortly - Quiz #1 handed back Tues - Homework #2 scores by Tues - Homework #3 available tonight (groups of 2) - Starting Tues, lecture notes on web page by 7 am day of class ********** Topic: I. Amortized analysis a. definition and motivation b. example of counter c. three methods d. example of doubling-array for stack ********** Amortized analysis: the time to perform a sequence of data-structure operations is averaged over all the operations performed. E.g., Perform sequence of operations (e.g., searches) with cost 1,1,10,1,1,1,2,1,2,1,1 - Traditional worst-case-per-operation analysis: 10 - Amortized analysis: (1+1+10+...+1)/11 = 22/11 = 2 per-operation Amortized bound f(n) --> guaranteed that no matter what sequence of n operations are performed, the total time will be <= f(n) * n. How does this differ from average case analysis? - average case analysis determines average operation cost over a probability distribution on the inputs. - amortized: determines average over a sequence of operations. Motivation is that traditional worst-case-per-operation analysis can give overly pessimistic bound when the only way of having an expensive operation is to have a lot of cheap ones before it. ********** Example: a binary counter Say we want to store a big binary counter in an array A: Start all entries at 0. Sequence of increment operations. The "algorithm" for deciding which bits to flip is we just start at the right and keep flipping until we flip a 0 to 1. Time cost: 1 for each bit flipped. counter time total A[m-1] A[m-2] ...... A[3] A[2] A[1] A[0] value cost cost ---------------------------------------- ----- ---- ----- 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 2 2 3 0 0 0 0 1 1 3 1 4 0 0 0 1 0 0 4 3 7 0 0 0 1 0 1 5 1 8 0 0 0 1 1 0 6 2 10 0 0 0 1 1 1 7 1 11 0 0 1 0 0 0 8 4 15 In a sequence of n (< 2^m) increments, worst-case cost per increment is? O(lg n) since at worst we flip lg(n)+1 bits. - Yields pessimistic bound of O(n lg n) for all operations But, what is an upper bound on the *amortized* cost per increment? Answer: 2 Proof: how often do we flip A[0]? Answer: every time. how often do we flip A[1]? Answer: every other time. How often do we flip A[2]? Answer: every 4th time. Etc. So, total cost spent on flipping A[0] is n, total cost of A[1] is floor(n/2), total cost on A[2] is floor(n/4), etc. total cost = sum_{i=0}^{floor(lg n)} floor(n/(2^i)) So, in worst case, n is a power of 2, and total time cost = sum{i=0}^{lg n} n/(2^i) = n(2 - 1/n) = 2n - 1 Thus amortized cost = (2n-1)/n < 2, i.e. O(1) amortized per increment. ********** Previous analysis is what the book calls the "aggregate method" of amortized analysis - Compute upper bound T(n) on worst case total cost of sequence of n operations - amortized bound is T(n)/n - imprecise compared with other methods: don't get separate cost for each type of operation ********** Second approach: "Accounting method" of amortized analysis - Consider a bank account used to pay for operations. - You make deposits with each operation. - Actual operation costs are deducted from the account. - Balance must not go negative. - Compute upper bound on amount deposited per operation: this is amortized bound Useful if accounting for amount deposited is easier than accounting for amounts deducted. Consider another proof for the binary counter: Proof 2: You make $2 deposits every time you flip 0 --> 1. $1 deducted for each bit flipped. Total deposited: $2n Why? each increment flips exactly one bit from 0 to 1. Claim: balance >= 0. Why? - There is $1 net to the account each flip 0 --> 1 - There is -$1 net to the account each flip 1 --> 0 - Thus $1 in the bank for each i with A[i]=1. - Amount in bank at any time >= charge on single increment for all flips 1 --> 0, and flips 0 --> 1 only increase the account. Thus amortized bound: 2 ********** Third approach: "Potential method" Let D_i = data structure after i'th operation - select potential function Phi : Data structure -> Real number - require: for all i, Phi(D_i) >= Phi(D_0) - amortized-cost_i = actual-cost_i + Phi(D_i) - Phi(D_{i-1}) - compute upper bound U on amortized-cost_i over all i: this is amortized bound Proof: let c_i = actual-cost_i, c'_i = amortized-cost_i, and let U be amortized bound. Must show sum_i c_i/n <= U. sum_i c_i/n = (1/n)*sum_{i=1}^n (c'_i + Phi(D_{i-1}) - Phi(D_i)) = (1/n)*(sum_i c'_i + Phi(D_0) - Phi(D_n)) why? other terms cancel <= (1/n) * sum_i U + (Phi(D_0) - Phi(D_n))/n = U + (Phi(D_0) - Phi(D_n))/n <= U why? Phi(D_n) >= Phi(D_0) QED Consider a third proof for the binary counter: Proof 3: Let Phi(D_i) = number of 1's in A after i'th increment. Check: For all i, Phi(D_i) >= Phi(D_0) why? Phi(D_0) = 0, Phi(D_i) >= 0. Suppose low order bits of counter are 0 followed by k 1's. Then actual-cost to increment = k+1 Before: x+k 1's for some x >= 0 After: x+1 1's Thus amortized-cost c'_i = c_i + Phi(D_i) - Phi(D_{i-1}) = (k+1) + (x+1) - (x+k) = 2 QED [Why exactly 2? (Phi(D_n) - Phi(D_0))/n >= 1/n term ignored] ********** Example: Doubling array Goal: Implement a stack using an array, without wasting too much space for the array. - have stack with push and pop operations. Internally represent as array of some size m, with pointer "top" giving top of stack. - to push, we just store in A[top++]. To pop we return A[--top]. Takes O(1) time. - if we ever fill up the array, we allocate a new array of double the size, copy over the contents of the old one, and let m <- 2m. (and free up old array). This takes time O(m). Amortized bound (asymptotic): Can use aggregate method: Total cost for pushes and pops is O(n). Total cost for doubling is at worst O(n + n/2 + n/4 + ....) = O(n). Why? consider all pushes So, amortized cost per operation is O(1). ********** Suppose we also wish to shrink the array whenever the stack gets too small. Goals: - the load factor (= # of items in the stack / array_size ) is >= constant c, (e.g., c = 1/4) - amortized cost of push or pop is <= constant c' (e.g., c' = 3) [Note: The above defn of load factor is the correct one. In the lecture, the numerator and denominator were reversed.] Stack overflows Array -> double array (as before) Idea: Array < 1/2 full -> halve array Keeps load within factor of 2. But bad for amortized time. Why? Start with m elements in stack (m = power of 2) Then push [doubles], pop, pop [halves], push, push [doubles], etc Better idea: Array <= 1/4 full -> halve array Keeps load within a factor of 4 Amortized bound? Can use accounting method: - Deposit $3 for push, $2 for pop - Charged $1 for push or pop - Associate $2 net with a push with the element. - When double from m to 2m, charge $1 for each element copied. - to copy A[i], for i <= m/2, charge element A[i+m/2] for i > m/2, charge element A[i] - Account has $2 for every element in stack that has not been copied, $1 for element A[0], and $0 for every other element in stack that has been copied. before after A[0] $1 $1 A[1] $0 $0 A[2] $0 $0 E.g., m=8: element in A[7] pays to copy itself A[3] $0 $0 and element in A[3], as indicated by --- A[4] $2 / $0 A[5] $2 / $0 A[6] $2 / $0 A[7] $2 --- $0 A[8] $2 [ Stopped here in the lecture ] - Account has >= $1 for every slot emptied due to deletion. Why? pop = $1 net and since emptied, popped at least one element from this slot. - When halve, know that A[m/4]..A[m/2] are emptied slots. Why? element A[m/2] inserted when doubled, now popping A[m/4] - to copy A[i], i=0,...,m/4 - 1, charge empty slot A[i+m/4] when before after doubled halved halved A[0] $1 $1 $1 A[1] $0 $0 / $0 A[2] $0 $0 / $0 E.g., m=16: slot A[4] pays to copy A[3] $0 $0 / $0 element in A[0], as indicated by --- A[4] $0 $1 (empty) A[5] $0 $1 (empty) A[6] $0 $1 (empty) A[7] $0 $1 (empty) A[8] $2 $1 (empty) ... A[15] Thus balance does not go negative. Amortized bound = 3