6.046J Lecture 11: Amortized Analysis

Lecture 11 Amortized Analysis Supplemental reading in CLRS: Chapter 17 Data structures typically support several different types of operations, each with its own cost (e.g., time cost or space cost). The idea behind amortized analysis is that, even when expensive operations must be performed, it is often possible to get away with performing them rarely, so that the average cost per operation is not so high. It is important to realize that these “average costs” are not expected values—there needn’t be any random events.1 Instead, we are considering the worst-case average cost per operation in a sequence of many operations. In other words, we are interested in the asymptotic behavior of the function C(n) = ¢ 1 ¡ · worst-case total cost of a sequence of n operations n (possibly with some condition on how many times each type of operation may occur). “Worst-case” means that no adversary could choose a sequence of n operations that gives a worse running time. In this lecture we discuss three methods of amortized analysis: aggregate analysis, the accounting method, and the potential method. 11.1 Aggregate Analysis In aggregate analysis, one assumes that there is no need to distinguish between the different operations on the data structure. One simply asks, what is the cost of performing a sequence of n operations, of any (possibly mixed) types? Example. Imagine a stack2 S with three operations: • P USH(S, x) – Θ(1) – pushes object x onto the stack • P OP(S) – Θ(1) – pops and returns the top object of S 1 There could be random events, though. It makes sense to talk about the worst-case amortized expected running time of a randomized algorithm, for example: one considers the average expected cost per operation in the string of operations which has the longest expected running time. 2 A stack is a data structure S with two primitive operations: P USH(S, x), which stores x, and P OP(S), which removes and returns the most recently pushed object. Thus, a stack is “last in, first out,” whereas a queue is “first in, first out.” • M ULTIPOP(S, k) – Θ (min {|S | , k}) – pops the top k items from the stack (or until empty) and returns the last item: while S is not empty and k > 0 do x ← P OP(S) k ← k−1 return x Suppose we wish to analyze the the running time for a sequence of n P USH, P OP, and M ULTIPOP operations, starting with an empty stack. Considering individual operations without amortization, we would say that a M ULTIPOP operation could take Θ (|S |) time, and |S | could be as large as n − 1. So in the hypothetical worst case, a single operation could take Θ(n) time, and n such operations ¡ ¢ strung together would take Θ n2 time. However, a little more thought reveals that such a string of operations is not possible. While a single P OP could take Θ(n) time, it would have to be preceded by Θ(n) P USH operations, which are cheap. Taken together, the Θ(n) P USH operations and the one M ULTIPOP operation take Θ(n) · Θ(1) + 1 · Θ(n) = Θ(n) time; thus, each operation in the sequence takes Θ(1) time on average. In general, if there occur r M ULTIPOP operations with arguments k 1 , . . . , k r , then there must also occur at least k 1 +· · ·+ k r P USH operations, so that there are enough items in the stack to pop. (To simplify notation, we assume that k is never chosen larger than |S |.) Thus, in a string of n operations, the total cost of all non-O(1) operations is bounded above by O(n), so the total cost of all operations is O(n) · O(1) + O(n) = O(n). Thus, the amortized running time per operation is O(1). 11.2 Accounting Method Unlike aggregated analysis, the accounting method assigns a different cost to each type of operation. The accounting method is much like managing your personal finances: you can estimate the costs of your operations however you like, as long as, at the end of the day, the amount of money you have set aside is enough to pay the bills. The estimated cost of an operation may be greater or less than its actual cost; correspondingly, the surplus of one operation can be used to pay the debt of other operations. In symbols, given an operation whose actual cost is c, we assign an amortized (estimated) cost cb. The amortized costs must satisfy the condition that, for any sequence of n operations with actual costs c 1 , . . . , c n and amortized costs cb1 , . . . , cbn , we have n X i =1 cbi ≥ n X ci. i =1 As long as this condition is met, we know that the amortized cost provides an upper bound on the actual cost of any sequence of operations. The difference between the above sums is the total surplus or “credit” stored in the data structure, and must at all times be nonnegative. In this way, the accounting model is like a debit account. Example. Perhaps you have bought pre-stamped envelopes at the post office before. In doing so, you pay up-front for both the envelopes and the postage. Then, when it comes time to send a letter, no additional charge is required. This accounting can be seen as an amortization of the cost of sending a letter: Lec 11 – pg. 2 of 8 Operation Buy an envelope Mail a letter Actual cost c i 5¢ 44¢ Amortized cost cbi 49¢ 0¢ Obviously, for any valid sequence of operations, the amortized cost is at least as high as the actual cost. However, the amortized cost is easier to keep track of—it’s one fewer item on your balance sheet. Example. For the stack in Section 11.1, we could assign amortized costs as follows: Operation P USH P OP M ULTIPOP Actual cost c i 1 1 min {|S | , k} Amortized cost cbi 2 0 0 When an object is pushed to the stack, it comes endowed with enough credit to pay not only for the operation of pushing it onto the stack, but also for whatever operation will eventually remove it from the stack, be that a P OP, a M ULTIPOP, or no operation at all. 11.3 Potential Method The potential method is similar in spirit to the accounting method. Rather than assigning a credit to each element of the data structure, the potential method assigns a credit to the entire data structure as a whole. This makes sense when the total credit stored in the data structure is a function only of its state and not of the sequence of operations used to arrive at that state. We think of the credit as a “potential energy” (or just “potential”) for the data structure. The strategy is to define a potential function Φ which maps a state D to a scalar-valued potential Φ(D). Given a sequence of n operations with actual costs c 1 , . . . , c n , which transform the data structure from its initial state D 0 through states D 1 , . . . , D n , we define heuristic costs cbi = c i + Φ (D i ) − Φ (D i−1 ) . This rule can be seen as the conservation of energy: it says that the surplus (or deficit) cost cbi − c i caused by a given operation must be equal to the change in potential of the data structure caused by that operation. An operation which increases the potential of the system is assigned a positive heuristic cost, whereas an operation which decreases the potential of the system is assigned a negative heuristic cost. Summing the heuristic costs of all n operations, we find n X i =1 cbi = n X à = c i + Φ (D i ) − Φ (D i−1 ) (a telescoping sum) i =1 n X ! c i + Φ (D n ) − Φ (D 0 ) . i =1 Thus, the total credit stored in the data structure is Φ (D n ) − Φ (D 0 ). This quantity must remain nonnegative at all times in order to ensure that the amortized cost provides an upper bound on the actual cost of any sequence of operations. (Any function Φ which satisfies this property can be used as the potential function.) One often chooses the potential function Φ so that Φ (D 0 ) = 0; then one must check that Φ remains nonnegative at all times. Lec 11 – pg. 3 of 8 Example. Continuing the stack example from Sections 11.1 and 11.2, we define the potential of a stack S to be Φ(S) = |S |, the number of elements in the stack. An empty stack has zero potential, and clearly Φ is always nonnegative, so Φ is an admissible potential function. Then the heuristic costs of the stack operations are as follows: • A P USH operation increases the size of S by 1, and has actual cost c P USH = 1. Thus, the amortized cost of a P USH operation is cbP USH = c P USH + Φ (D new ) − Φ (D old ) = 1 + (|S old | + 1) − |S old | = 2. • A P OP operation decreases the size of S by 1, and has actual cost c P OP = 1. Thus, the amortized cost of a P OP operation is cbP OP = c P OP + Φ (D new ) − Φ (D old ) = 1 + (|S old | − 1) − |S old | = 0. • The operation M ULTIPOP(S, k) decreases the size of S by min {|S | , k}, and has actual cost c M ULTIPOP = min {|S | , k}. Thus, the amortized cost of a M ULTIPOP operation is cbM ULTIPOP = c M ULTIPOP + Φ (D new ) − Φ (D old ) = min {|S | , k} + (|S new | − |S old |) = 0. Thus, the amortized costs for this application of the potential method are the same as those we came up with using the accounting method in Section 11.2: Operation P USH P OP M ULTIPOP 11.4 Actual cost c i 1 1 min {|S | , k} Amortized cost cbi 2 0 0 Example: A Dynamically Resized Table We now extend the example we started in Lecture 10: a dynamically doubled table T. This time we will forget about keys, inserting each new value into the next available block in the array T.arr. If T.arr is full, then we create a new array of size 2 |T.arr|, copy over the old elements of T, perform the insertion, and reassign T.arr to point to that array. Likewise, in §11.4.5 we ask you to devise an extension of our data structure which supports deletions (specifically, pops) as well as insertions, and halves the array T.arr when appropriate in addition to doubling it when appropriate. In this way, T never takes up much more space than it has to. For now, assume that T only supports insertions and lookups. We will store in T two things: the underlying array T.arr, and an integer T.num which keeps track of the number of entries in T.arr which have yet been populated. Thus, the array is full and needs to be doubled upon the next insertion if and only if |T.arr| = T.num. So the table lookup will be a simple array lookup operation, which takes O(1) time, and the insertion operation will be defined as follows: Lec 11 – pg. 4 of 8 Algorithm: T ABLE -I NSERT(T, x) 1 2 3 4 5 6 7 8 9 10 11.4.1 if |T.arr| = 0 then T.arr ← new array of size 1 B If table is full, double it if T.num = |T.arr| then arr0 ← new array of size 2 |T.arr| Migrate all items from T.arr to arr0 T.arr ← arr0 B Insert x into the array T.arr[T.num] ← x T.num ← T.num + 1 Actual cost per operation A lookup operation on T is simply an array lookup, which takes O(1) time. The running time of T ABLE -I NSERT, on the other hand, depends on whether the table needs to be doubled, which depends on the number of insertions which have happened prior to the current one. Specifically, starting from an initial table of size zero, the cost c i of the ith insertion is   1 if the table has space        i − 1 to allocate the new table      i − 1 to migrate the old entries ci =    Θ (i) if the table has to be expanded:      1 to make the insertion       1 to reassign T.arr The “Chicken Little” analysis would say that the worst possible string of n operations would consist entirely of operations which have the worst-case single-operation running time Θ(i), so that the sequence has running time ¡ ¢ ¡ ¢ Θ 1 + 2 + · · · + n = Θ n2 . This bound is not tight, however, because it is not possible for every operation to be worst-case. 11.4.2 Aggregate analysis Aggregate analysis of our table’s operations amounts to keeping track of precisely which operations will be worst-case. The table has to be expanded if and only if the table is full, so ( ci = Θ(i) if i − 1 is zero or an exact power of 2 1 otherwise. Thus, a string of n operations, m of which are insertion operations, would take time ¡ ¢ ¡ ¢ T n − m lookups + T m insertions  ³¡ ´ X ¢  = n − m · Θ(1) +  Θ(1)  + k − 1 is not an exact power of 2 Lec 11 – pg. 5 of 8 X k − 1 is an exact power of 2  Θ(k) = ³¡ à ´ ¡ ¡ ¥ ¦¢¢ n − m · Θ(1) + m − 2 + lg(m − 1) · Θ(1) ¢ + blg(m X−1)c ³ ´ Θ 2j ! j =0 ¢ = Θ(n − m) + Θ(m) − Θ(lg m) + Θ(2m) ¡ = Θ(n) + Θ(m) = Θ(n) (since m ≤ n). Thus, a string of n operations takes Θ(n) time, regardless of how many of the operations are insertions and how many are lookups. Thus, aggregate analysis gives an amortized running time of O(1) per operation. 11.4.3 Accounting analysis We can set up a balance sheet to pay for the operations on our table as follows: • Lookups cost $1 • Insertions cost $3 – $1 to insert our element into the array itself – $2 to save up for the next time the array has to be expanded * One dollar will pay for migrating the element itself * One dollar will go to charity. Because the current incarnation of T.arr started with 12 |T.arr| elements pre-loaded, it follows that, when T.arr is full, only 21 |T.arr| elements will have enough money in the bank to pay for their migration. However, there will also be $ 21 |T.arr| of charity money saved up from the 21 |T.arr| most recent insertions. This charity is exactly sufficient to pay for migrating the elements that don’t have their own money. Thus, our balance sheet checks out; our assigned costs of $1 and $3 work. In particular, each operation’s cost is O(1). 11.4.4 Potential analysis In our potential analysis, the potential energy will play the role of money in the bank: when the array needs to be doubled, the potential energy will exactly pay for migrating the old elements into the new array. Thus, we want to find a function which equals zero immediately after doubling the table and grows to size |T.arr| as it is filled up. (To simplify notation, assume that copying an array of size k takes exactly k steps, rather than always using the more precise notation Θ(k).) The simplest function which satisfies these properties, and the one that will be most convenient to work with, is Φ(T) = 2 · T.num − |T.arr| . Right after expansion, we have T.num = 21 |T.arr|, so Φ(T) = 0; right before expasnion, we have T.num = |T.arr|, so Φ(T) = 2 · |T.arr| − |T.arr| = |T.arr|. The actual cost of a lookup is, as we said, c lookup = 1. (Again, to simplify notation, let’s just write 1 instead of Θ(1).) Using the potential Φ, the amortized cost of a lookup is cblookup = c lookup + Φ (Tnew ) − Φ (Told ) = c lookup = 1, Lec 11 – pg. 6 of 8 since Tnew = Told . To find the amortized cost of an insertion, we must split into cases. In the first case, suppose the table does not need to be doubled as a result of the insertion. Then the amortized cost is cb = c + Φ (Tnew ) − Φ (Told ) ¡ ¢ ¡ ¢ = 1 + 2 · Tnew .num − |Tnew .arr| − 2 · Told .num − |Told .arr| ¡ ¢ ¡ ¢ = 1 + 2 Tnew .num − Tnew .num − |Tnew .arr| − |Told .arr| = 1 + 2(1) + 0 = 3. In the second case, suppose the table does need to be doubled as a result of the insertion. Then the actual cost of insertion is |Tnew .num|, so the amortized cost of insertion is cb = c + Φ (Tnew ) − Φ (Told ) ¡ ¢ ¡ ¢ = Tnew .num + 2 · Tnew .num − |Tnew .arr| − 2 · Told .num − |Told .arr| ¡ ¢ ¡ ¢ ¡ ¢ = |Told .arr| + 1 + 2 Tnew .num − Told .num − |Tnew .arr| − |Told .arr| ¡ ¢ ¡ ¢ = |Told .arr| + 1 + 2(1) − 2 |Told .arr| − |Told .arr| = 3. In both cases, the amortized running time of insertion is 3. (If we had picked a less convenient potential function Φ, the amortized running time would probably be different in the two cases. The potential analysis would still be valid if done correctly, but the resulting amortized running times probably wouldn’t be as easy to work with.) 11.4.5 Exercise: Allowing deletions Suppose we wanted our dynamically resized table to support pops (deleting the most recently inserted element) as well as insertions. It would be reasonable to want the table to halve itself when fewer than half the slots in the array are occupied, so that the table only ever takes up at most twice the space it needs to. Thus, a first attempt at a pop functionality might look like this (with the T ABLE -I NSERT procedure unchanged): Algorithm: N AÏVE -P OP(T) 1 2 3 4 5 6 7 8 9 10 if T.num = 0 then error “Tried to pop from an empty table” r ← T.arr[T.num − 1] Unset T.arr[T.num − 1] T.num ← T.num − 1 if T.num ≤ 21 |T.arr| then ¥ ¦ arr0 ← new array of size 12 |T.arr| Migrate all items from T.arr to arr0 T.arr ← arr0 return r Lec 11 – pg. 7 of 8 Unfortunately, the worst-case running time of N AÏVE -P OP is not so good. Exercise 11.1. Given n sufficiently large, produce a sequence of n T ABLE -I NSERT, lookup, and/or ¡ ¢ N AÏVE -P OP operations which have total running time Θ n2 . Thus, in any amortized analysis, at least one of the operations must have amortized running time at least Ω (n). Exercise 11.2. Devise a way of supporting pops which still retains O(1) worst-case amortized running time for each operation, and do an amortized analysis to prove that this is the case. You may redefine T ABLE -I NSERT or add more data fields to T if you wish (and of course you will have to define T ABLE -P OP), but it must still remain the case that, for every possible sequence of operations, T only takes up O (T.num) space in memory at any given point in time. [Hint: An adversary can choose a series of operations for which T ABLE -I NSERT and N AÏVE -P OP run slowly by making sure T.num repeatedly crosses the critical thresholds for table doubling and table halving. (You must have used this fact somehow in your solution to Exercise 11.1.) So your first step will be to figure out how to place decisions about doubling and halving outside the control of your adversary.] Lec 11 – pg. 8 of 8