Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 14 Prof. Charles E. Leiserson Introduction to Algorithms Day 24 L14.2? 2001 by Charles E. Leiserson How large should a hash table be? Problem: What if we don’t know the proper size in advance? Goal: Make the table as small as possible, but large enough so that it won’t overflow (or otherwise become inefficient). IDEA: Whenever the table overflows, “grow” it by allocating (via malloc or new) a new, larger table. Move all items from the old table into the new one, and free the storage for the old table. Solution: Dynamic tables. Introduction to Algorithms Day 24 L14.3? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 1 2. INSERT overflow Introduction to Algorithms Day 24 L14.4? 2001 by Charles E. Leiserson 1 1 Example of a dynamic table 1. INSERT 2. INSERT overflow Introduction to Algorithms Day 24 L14.5? 2001 by Charles E. Leiserson 1 1 2 Example of a dynamic table 1. INSERT 2. INSERT Introduction to Algorithms Day 24 L14.6? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 1 1 2 2 3. INSERT overflow Introduction to Algorithms Day 24 L14.7? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 2 1 overflow Introduction to Algorithms Day 24 L14.8? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 2 1 Introduction to Algorithms Day 24 L14.9? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 4 3 2 1 Introduction to Algorithms Day 24 L14.10? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT 4 3 2 1 overflow Introduction to Algorithms Day 24 L14.11? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT 4 3 2 1 overflow Introduction to Algorithms Day 24 L14.12? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 5. INSERT 4 3 2 1 Introduction to Algorithms Day 24 L14.13? 2001 by Charles E. Leiserson Example of a dynamic table 1. INSERT 2. INSERT 3. INSERT 4. INSERT 6. INSERT 6 5. INSERT 5 4 3 2 1 7 7. INSERT Introduction to Algorithms Day 24 L14.14? 2001 by Charles E. Leiserson Worst-case analysis Consider a sequence of n insertions. The worst-case time to execute one insertion is Θ(n). Therefore, the worst-case time for n insertions is n ·Θ(n) = Θ(n 2 ). WRONG! In fact, the worst-case cost for n insertions is only Θ(n) ?Θ(n 2 ). Let’s see why. Introduction to Algorithms Day 24 L14.15? 2001 by Charles E. Leiserson Tighter analysis i 12345678910 size i 1 2 4 4 8 8 8 8 16 16 c i 1231511191 Let c i = the cost of the i th insertion = i if i –1is an exact power of 2, 1 otherwise. Introduction to Algorithms Day 24 L14.16? 2001 by Charles E. Leiserson Tighter analysis Let c i = the cost of the i th insertion = i if i –1is an exact power of 2, 1 otherwise. i 12345678910 size i 1 2 4 4 8 8 8 8 16 16 1111111111 12 4 8 c i Introduction to Algorithms Day 24 L14.17? 2001 by Charles E. Leiserson Tighter analysis (continued) ?? )( 3 2 )1lg( 0 1 n n n c n j j n i i Θ= ≤ +≤ = ∑ ∑ ? = = Cost of n insertions . Thus, the average cost of each dynamic-table operation is Θ(n)/n = Θ(1). Introduction to Algorithms Day 24 L14.18? 2001 by Charles E. Leiserson Amortized analysis An amortized analysis is any strategy for analyzing a sequence of operations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive. Even though we’re taking averages, however, probability is not involved! ? An amortized analysis guarantees the average performance of each operation in the worst case. Introduction to Algorithms Day 24 L14.19? 2001 by Charles E. Leiserson Types of amortized analyses Three common amortization arguments: ? the aggregate method, ? the accounting method, ? the potential method. We’ve just seen an aggregate analysis. The aggregate method, though simple, lacks the precision of the other two methods. In particular, the accounting and potential methods allow a specific amortized cost to be allocated to each operation. Introduction to Algorithms Day 24 L14.20? 2001 by Charles E. Leiserson Accounting method ? Charge i th operation a fictitious amortized cost ? i , where $1 pays for 1 unit of work (i.e., time). ? This fee is consumed to perform the operation. ? Any amount not immediately consumed is stored in the bank for use by subsequent operations. ? The bank balance must not go negative! We must ensure that ∑∑ == ≤ n i i n i i cc 11 ? for all n. ? Thus, the total amortized costs provide an upper bound on the total true costs. Introduction to Algorithms Day 24 L14.21? 2001 by Charles E. Leiserson $0 $0 $0 $0 $0 $0 $0 $0 $2 $2 $2 $2 Example: $2 $2 Accounting analysis of dynamic tables Charge an amortized cost of ? i =$3for the i th insertion. ? $1 pays for the immediate insertion. ? $2 is stored for later table doubling. When the table doubles, $1 pays to move a recent item, and $1 pays to move an old item. overflow Introduction to Algorithms Day 24 L14.22? 2001 by Charles E. Leiserson Example: Accounting analysis of dynamic tables Charge an amortized cost of ? i =$3for the i th insertion. ? $1 pays for the immediate insertion. ? $2 is stored for later table doubling. When the table doubles, $1 pays to move a recent item, and $1 pays to move an old item. overflow $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 Introduction to Algorithms Day 24 L14.23? 2001 by Charles E. Leiserson Example: Accounting analysis of dynamic tables Charge an amortized cost of ? i =$3for the i th insertion. ? $1 pays for the immediate insertion. ? $2 is stored for later table doubling. When the table doubles, $1 pays to move a recent item, and $1 pays to move an old item. $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $2 $2 $2 Introduction to Algorithms Day 24 L14.24? 2001 by Charles E. Leiserson Accounting analysis (continued) Key invariant: Bank balance never drops below 0. Thus, the sum of the amortized costs provides an upper bound on the sum of the true costs. i 12345678910 size i 1 2 4 4 8 8 8 8 16 16 c i 1231511191 ? i 2333333333 bank i 1224246824 * *Okay, so I lied. The first operation costs only $2, not $3. Introduction to Algorithms Day 24 L14.25? 2001 by Charles E. Leiserson Potential method IDEA: View the bank account as the potential energy (àlaphysics) of the dynamic set. Framework: ? Start with an initial data structure D 0 . ? Operation i transforms D i–1 to D i . ? The cost of operation i is c i . ? Define a potential function Φ : {D i } →R, such that Φ(D 0 ) = 0 and Φ(D i ) ≥ 0 for all i. ? The amortized cost ? i with respect to Φ is defined to be ? i = c i + Φ(D i ) – Φ(D i–1 ). Introduction to Algorithms Day 24 L14.26? 2001 by Charles E. Leiserson Understanding potentials ? i = c i + Φ(D i ) – Φ(D i–1 ) potential difference ?Φ i ? If ?Φ i > 0, then ? i > c i . Operation i stores work in the data structure for later use. ? If ?Φ i < 0, then ? i < c i . The data structure delivers up stored work to help pay for operation i. Introduction to Algorithms Day 24 L14.27? 2001 by Charles E. Leiserson The amortized costs bound the true costs The total amortized cost of n operations is () ∑∑ = ? = Φ?Φ+= n i iii n i i DDcc 1 1 1 )()( ? Summing both sides. Introduction to Algorithms Day 24 L14.28? 2001 by Charles E. Leiserson The amortized costs bound the true costs The total amortized cost of n operations is () )()( )()( ? 0 1 1 1 1 DDc DDcc n n i i n i iii n i i Φ?Φ+= Φ?Φ+= ∑ ∑∑ = = ? = The series telescopes. Introduction to Algorithms Day 24 L14.29? 2001 by Charles E. Leiserson The amortized costs bound the true costs The total amortized cost of n operations is () ∑ ∑ ∑∑ = = = ? = ≥ Φ?Φ+= Φ?Φ+= n i i n n i i n i iii n i i c DDc DDcc 1 0 1 1 1 1 )()( )()( ? since Φ(D n ) ≥ 0 and Φ(D 0 ) = 0. Introduction to Algorithms Day 24 L14.30? 2001 by Charles E. Leiserson Potential analysis of table doubling Define the potential of the table after the ith insertion by Φ(D i ) = 2i –2 ?lg i? . (Assume that 2 ?lg 0? = 0.) Note: ? Φ(D 0 ) = 0, ? Φ(D i ) ≥ 0 for all i. Example: ? ? ? ? ? ? ? ? ? ? ? ? Φ = 2·6 – 2 3 = 4 $0 $0 $0 $0 $0 $0 $0 $0 $2 $2 $2 $2 accounting method)( Introduction to Algorithms Day 24 L14.31? 2001 by Charles E. Leiserson Calculation of amortized costs The amortized cost of the i th insertion is ? i = c i + Φ(D i ) – Φ(D i–1 ) i + (2i –2 ?lg i? ) – (2(i–1) – 2 ?lg (i–1)? ) if i –1is an exact power of 2, 1 + (2i –2 ?lg i? ) – (2(i–1) – 2 ?lg (i–1)? ) otherwise. = Introduction to Algorithms Day 24 L14.32? 2001 by Charles E. Leiserson Calculation (Case 1) Case 1: i –1is an exact power of 2. ? i = i + (2i –2 ?lg i? ) – (2(i–1) – 2 ?lg (i–1)? ) = i + 2 – (2 ?lg i? –2 ?lg (i–1)? ) = i + 2 – (2(i –1) –(i –1)) = i + 2 – 2i + 2 + i –1 = 3 Introduction to Algorithms Day 24 L14.33? 2001 by Charles E. Leiserson Calculation (Case 2) Case 2: i –1is not an exact power of 2. ? i = 1 + (2i –2 ?lg i? ) – (2(i–1) – 2 ?lg (i–1)? ) =1 + 2 –(2 ?lg i? –2 ?lg (i–1)? ) = 3 Therefore, n insertions cost Θ(n) in the worst case. Exercise: Fix the bug in this analysis to show that the amortized cost of the first insertion is only 2. Introduction to Algorithms Day 24 L14.34? 2001 by Charles E. Leiserson Conclusions ? Amortized costs can provide a clean abstraction of data-structure performance. ? Any of the analysis methods can be used when an amortized analysis is called for, but each method has some situations where it is arguably the simplest. ? Different schemes may work for assigning amortized costs in the accounting method, or potentials in the potential method, sometimes yielding radically different bounds.