AlgoScope

Amortized Analysis

Average cost per operation over a sequence, even when a few operations are expensive.

Complexity analysis, analysis, intermediate
Append 1 costs 1, average 1.0.123456789101112costsumavg111.0

Complexity in Numbers: Appends to a doubling array

Decision, step 2 of 14

Append 1: room for it, one write. Cost 1, total 1, average 1.0.

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.