AlgoScope

Potential Method

A potential function on the data structure state pays for expensive operations.

Complexity analysis, analysis, advanced
Append 1: cost 1, phi 1, amortized 2.123456789101112costphiamortized112

Complexity in Numbers: Potential method: every append costs the same

Decision, step 2 of 14

Append 1: real cost 1. phi goes from 0 to 2 x 1 - 1 = 1, a change of 1. Amortized cost = 1 + (1) = 2.

How complexity in numbers works

Cost

Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Complexity in Numbers covers these too, in the same run.