Potential Method
A potential function on the data structure state pays for expensive operations.
Decision · step 2 of 14Complexity 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.
What you will see
A potential gauge rises with cheap operations and drops during expensive ones.
Cost
| Space | O(1) |
|---|
How you work with it here
explore, compare two runs, run it on your own input.
Screen readers: Growth curves are described in words and as a table of operation counts for sample input sizes; each concept has a one-sentence spoken definition.
Reduced motion: Curves and counters update without animation.
Before this
Related
Taught by the same lesson
Complexity in Numbers covers these too, in the same run.