Amortized Analysis of Rehashing
What is rehashing
Assumptions for Thursday, Feb. 10, 2000
Observations
Amortized analysis Strategy 1: add up operations
Amortized analysis Strategy 2: Accounting Method
Accounting Method analysis
Slide 9
Slide 10
Potential function
Tokens as a potential function
The Math
Potential method analysis