Potential Method
A potential function on the data structure state pays for expensive operations.
Complexity in Numbers: Potential method: every append costs the same
Append 1: real cost 1. phi goes from 0 to 2 x 1 - 1 = 1, a change of 1. Amortized cost = 1 + (1) = 2.
Cost
- Space
- O(1)
Before this
Related
Leads to
Topics that need this one first.
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.