Amortized Analysis
Sometimes slow, never slow for long
Some operations are cheap almost every time and expensive once in a while. A growing array's append usually writes one value, but when the array is full it copies every value into a bigger block first. A stack loop that waits for a bigger value usually pops nothing, and then one value arrives that pops everything waiting.
Judge each operation by its worst moment and both look O(n). Add up the whole run and both are O(n) in total, O(1) per operation. Amortized analysis is that second way of counting: bound the total cost of any sequence of operations, then divide by how many there are. This lesson counts both examples on our judge, gives the two standard ways to prove a bound (the total, and coins in a bank), shows how the bank can run dry, and where amortized costs turn up in the rest of the course.
A while inside a for that's still O(n)
Next Greater Element: for each value, the next bigger value to its right. The stack holds the values still waiting for one, and each new value pops every smaller value off the top, because it's their answer. Here the input falls from n − 1 down to 1, so nothing is popped until the last value, n, which pops all of them:
#include <bits/stdc++.h>
using namespace std;
int main() {
for (int n : {100000, 200000, 400000}) {
vector<int> nums;
for (int v = n - 1; v >= 1; v--) nums.push_back(v); // falling,
nums.push_back(n); // then one value bigger than all of them
vector<int> answer(n, -1), stack; // indexes still waiting for a bigger value
long long pushes = 0, pops = 0, most = 0;
for (int i = 0; i < n; i++) {
long long popped = 0;
while (!stack.empty() && nums[stack.back()] < nums[i]) {
answer[stack.back()] = nums[i];
stack.pop_back();
popped++;
}
stack.push_back(i);
pushes++;
pops += popped;
most = max(most, popped);
}
printf("n = %d: %lld pushes, %lld pops, the most in one step %lld\n", n, pushes, pops, most);
}
}
// n = 100000: 100000 pushes, 99999 pops, the most in one step 99999
// n = 200000: 200000 pushes, 199999 pops, the most in one step 199999
// n = 400000: 400000 pushes, 399999 pops, the most in one step 399999def next_greater(nums): # for each value, the next bigger one to its right (-1 if none)
answer = [-1] * len(nums)
stack = [] # indexes still waiting for a bigger value
pushes = pops = most = 0
for i, x in enumerate(nums):
popped = 0
while stack and nums[stack[-1]] < x:
answer[stack.pop()] = x
popped += 1
stack.append(i)
pushes += 1
pops += popped
most = max(most, popped)
return answer, pushes, pops, most
for n in (100000, 200000, 400000):
nums = list(range(n - 1, 0, -1)) + [n] # falling, then one value bigger than all of them
_, pushes, pops, most = next_greater(nums)
print(f"n = {n}: {pushes} pushes, {pops} pops, the most in one step {most}")
# n = 100000: 100000 pushes, 99999 pops, the most in one step 99999
# n = 200000: 200000 pushes, 199999 pops, the most in one step 199999
# n = 400000: 400000 pushes, 399999 pops, the most in one step 399999import java.util.*;
public class Main {
public static void main(String[] args) {
for (int n : new int[]{100000, 200000, 400000}) {
int[] nums = new int[n];
for (int i = 0; i < n - 1; i++) nums[i] = n - 1 - i; // falling,
nums[n - 1] = n; // then one value bigger than all of them
int[] answer = new int[n];
Arrays.fill(answer, -1);
ArrayDeque<Integer> stack = new ArrayDeque<>(); // indexes still waiting for a bigger value
long pushes = 0, pops = 0, most = 0;
for (int i = 0; i < n; i++) {
long popped = 0;
while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
answer[stack.pop()] = nums[i];
popped++;
}
stack.push(i);
pushes++;
pops += popped;
most = Math.max(most, popped);
}
System.out.printf("n = %d: %d pushes, %d pops, the most in one step %d%n", n, pushes, pops, most);
}
}
}
// n = 100000: 100000 pushes, 99999 pops, the most in one step 99999
// n = 200000: 200000 pushes, 199999 pops, the most in one step 199999
// n = 400000: 400000 pushes, 399999 pops, the most in one step 399999for (const n of [100000, 200000, 400000]) {
const nums = [];
for (let v = n - 1; v >= 1; v--) nums.push(v); // falling,
nums.push(n); // then one value bigger than all of them
const answer = new Array(n).fill(-1), stack = []; // indexes still waiting for a bigger value
let pushes = 0, pops = 0, most = 0;
for (let i = 0; i < n; i++) {
let popped = 0;
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
answer[stack.pop()] = nums[i];
popped++;
}
stack.push(i);
pushes++;
pops += popped;
most = Math.max(most, popped);
}
console.log(`n = ${n}: ${pushes} pushes, ${pops} pops, the most in one step ${most}`);
}
// n = 100000: 100000 pushes, 99999 pops, the most in one step 99999
// n = 200000: 200000 pushes, 199999 pops, the most in one step 199999
// n = 400000: 400000 pushes, 399999 pops, the most in one step 399999One step popped n − 1 values, 99,999 at n = 100,000. Yet the whole run made n pushes and n − 1 pops, 2n − 1 steps: every index is pushed once and popped at most once, so the while loop can't run more than n times across the whole run, however the pops fall. That's O(n) in total and O(1) per value, amortized. Monotonic Stack: Next Greater and Smaller Elements and the sliding window (Introduction to Sliding Window) rely on this same count.
The total over the run
An array that doubles when full, with each append's cost counted: 1 for the write, plus 1 for every value copied to the bigger block:
#include <bits/stdc++.h>
using namespace std;
struct GrowingArray { // doubles its block when it's full
int* block = new int[1]; // room for 1
long long capacity = 1, size = 0;
long long append(int x) { // returns what this append cost: 1 write, plus any copies
long long cost = 1;
if (size == capacity) {
int* bigger = new int[2 * capacity];
for (long long i = 0; i < size; i++) bigger[i] = block[i];
delete[] block;
block = bigger;
capacity *= 2;
cost += size;
}
block[size++] = x;
return cost;
}
~GrowingArray() { delete[] block; }
};
int main() {
for (int n : {1000, 1000000}) {
GrowingArray a;
long long total = 0, costliest = 0;
for (int i = 0; i < n; i++) {
long long c = a.append(i);
total += c;
costliest = max(costliest, c);
}
printf("n = %d: total %lld, %.3f per append, the costliest %lld\n", n, total, (double)total / n, costliest);
}
}
// n = 1000: total 2023, 2.023 per append, the costliest 513
// n = 1000000: total 2048575, 2.049 per append, the costliest 524289class GrowingArray: # doubles its block when it's full
def __init__(self):
self.block = [None] # room for 1
self.size = 0
def append(self, x): # returns what this append cost: 1 write, plus any copies
cost = 1
if self.size == len(self.block):
bigger = [None] * (2 * len(self.block))
for i in range(self.size):
bigger[i] = self.block[i]
self.block = bigger
cost += self.size
self.block[self.size] = x
self.size += 1
return cost
for n in (1000, 1000000):
a = GrowingArray()
costs = [a.append(i) for i in range(n)]
print(f"n = {n}: total {sum(costs)}, {sum(costs) / n:.3f} per append, the costliest {max(costs)}")
# n = 1000: total 2023, 2.023 per append, the costliest 513
# n = 1000000: total 2048575, 2.049 per append, the costliest 524289public class Main {
static class GrowingArray { // doubles its block when it's full
int[] block = new int[1]; // room for 1
int size = 0;
long append(int x) { // returns what this append cost: 1 write, plus any copies
long cost = 1;
if (size == block.length) {
int[] bigger = new int[2 * block.length];
for (int i = 0; i < size; i++) bigger[i] = block[i];
block = bigger;
cost += size;
}
block[size++] = x;
return cost;
}
}
public static void main(String[] args) {
for (int n : new int[]{1000, 1000000}) {
GrowingArray a = new GrowingArray();
long total = 0, costliest = 0;
for (int i = 0; i < n; i++) {
long c = a.append(i);
total += c;
costliest = Math.max(costliest, c);
}
System.out.printf("n = %d: total %d, %.3f per append, the costliest %d%n",
n, total, (double) total / n, costliest);
}
}
}
// n = 1000: total 2023, 2.023 per append, the costliest 513
// n = 1000000: total 2048575, 2.049 per append, the costliest 524289class GrowingArray { // doubles its block when it's full
constructor() {
this.block = new Array(1); // room for 1
this.size = 0;
}
append(x) { // returns what this append cost: 1 write, plus any copies
let cost = 1;
if (this.size === this.block.length) {
const bigger = new Array(2 * this.block.length);
for (let i = 0; i < this.size; i++) bigger[i] = this.block[i];
this.block = bigger;
cost += this.size;
}
this.block[this.size++] = x;
return cost;
}
}
for (const n of [1000, 1000000]) {
const a = new GrowingArray();
let total = 0, costliest = 0;
for (let i = 0; i < n; i++) {
const c = a.append(i);
total += c;
costliest = Math.max(costliest, c);
}
console.log(`n = ${n}: total ${total}, ${(total / n).toFixed(3)} per append, the costliest ${costliest}`);
}
// n = 1000: total 2023, 2.023 per append, the costliest 513
// n = 1000000: total 2048575, 2.049 per append, the costliest 524289The costliest append at n = 1,000 cost 513: it found 512 values in a full block and copied them all. But copies happen only at sizes 1, 2, 4, 8, …, 512, and they add up to 1 + 2 + 4 + … + 512 = 1,023, less than n. So the total is 1,000 writes plus 1,023 copies, 2,023, and the average is 2.023 per append. At a million appends the costliest copied 524,288 values, and the average was still 2.049.
This is the aggregate method: total the cost of the whole sequence and divide. Doubling keeps the copies under 2n, so n appends cost under 3n: O(1) per append, amortized. The factor doesn't have to be 2: Java's ArrayList grows by half, and any fixed factor gives a geometric sum. Growing by a fixed amount doesn't: the quiz below checks why.
Coins in the bank
The accounting method proves the same bound one operation at a time. Charge every operation the same number of coins. A cheap operation pays its cost and saves the rest; an expensive one spends the savings. If the bank never goes below zero, for any sequence, the total cost is at most the total charged, and the charge is the amortized cost.
- The stack: charge 2 per operation. A push costs 1 and saves 1, on the value it pushed; a pop of k values is paid by the k coins those values saved.
- The growing array: charge 3. An append costs 1 and saves 2. When a block of s values fills, the s/2 values appended since it last grew saved s coins between them, enough to copy all s.
We checked those charges by trying every sequence: 2 coins kept the stack's bank from going below zero through every sequence of 18 pushes and pops, and 1 didn't; 3 kept the array's through 300 appends, and 2 ran dry at append number 5.
Keep the Bank Positive. Pick a structure and a charge, then make the operations yourself and try to run the bank dry. The costs are the ones the structures really have; the bank is charge minus cost, added up.
The potential method, for the formal version: instead of coins on each value, keep one number Φ for the whole structure, the savings, and define an operation's amortized cost as its real cost plus the change in Φ. For the stack Φ is the number of values on it; for the doubling array, 2 × size − capacity. A push of the stack costs 1 and raises Φ by 1, so 2; popping k values costs k and lowers Φ by k, so 0. As long as Φ never drops below where it started, the amortized costs add up to at least the real ones. (The doubling array starts with room for 1 and nothing in it, so its Φ starts at −1, and from the first append on it stays above 0.)
When the bank runs dry
An array that shrinks at half full. Freeing memory when an array empties sounds sensible: halve the block when it falls to half full. But then an array that has just doubled is exactly at half: remove one value and it halves, copying everything; append one and it's full, so it doubles, copying everything again. Here are 1,024 values in a full block, then 10,000 rounds of append-and-remove:
#include <bits/stdc++.h>
using namespace std;
struct ShrinkingArray { // counts the values a real one would copy
double shrinkAt; // shrink when it falls to this share of its block: 1/2 or 1/4
long long capacity = 1, size = 0, copies = 0;
void append() {
if (size == capacity) {
capacity *= 2;
copies += size; // every value moves to the bigger block
}
size++;
}
void removeLast() {
size--;
if (capacity > 1 && size <= capacity * shrinkAt) {
capacity /= 2;
copies += size; // every value left moves to the smaller block
}
}
};
int main() {
for (double shrinkAt : {0.5, 0.25}) {
ShrinkingArray a{shrinkAt};
for (int i = 0; i < 1024; i++) a.append(); // full: 1024 values in a block of 1024
long long before = a.copies;
for (int i = 0; i < 10000; i++) { // then append one and remove it, 10,000 times
a.append();
a.removeLast();
}
printf("shrink at %g: %lld copies for 20000 operations\n", shrinkAt, a.copies - before);
}
}
// shrink at 0.5: 20480000 copies for 20000 operations
// shrink at 0.25: 1024 copies for 20000 operationsclass ShrinkingArray: # counts the values a real one would copy
def __init__(self, shrink_at): # shrink when it falls to this share of its block: 1/2 or 1/4
self.capacity, self.size, self.copies = 1, 0, 0
self.shrink_at = shrink_at
def append(self):
if self.size == self.capacity:
self.capacity *= 2
self.copies += self.size # every value moves to the bigger block
self.size += 1
def remove_last(self):
self.size -= 1
if self.capacity > 1 and self.size <= self.capacity * self.shrink_at:
self.capacity //= 2
self.copies += self.size # every value left moves to the smaller block
for shrink_at in (0.5, 0.25):
a = ShrinkingArray(shrink_at)
for _ in range(1024): # full: 1024 values in a block of 1024
a.append()
before = a.copies
for _ in range(10000): # then append one and remove it, 10,000 times
a.append()
a.remove_last()
print(f"shrink at {shrink_at}: {a.copies - before} copies for 20000 operations")
# shrink at 0.5: 20480000 copies for 20000 operations
# shrink at 0.25: 1024 copies for 20000 operationspublic class Main {
static class ShrinkingArray { // counts the values a real one would copy
double shrinkAt; // shrink when it falls to this share of its block: 1/2 or 1/4
long capacity = 1, size = 0, copies = 0;
ShrinkingArray(double shrinkAt) { this.shrinkAt = shrinkAt; }
void append() {
if (size == capacity) {
capacity *= 2;
copies += size; // every value moves to the bigger block
}
size++;
}
void removeLast() {
size--;
if (capacity > 1 && size <= capacity * shrinkAt) {
capacity /= 2;
copies += size; // every value left moves to the smaller block
}
}
}
public static void main(String[] args) {
for (double shrinkAt : new double[]{0.5, 0.25}) {
ShrinkingArray a = new ShrinkingArray(shrinkAt);
for (int i = 0; i < 1024; i++) a.append(); // full: 1024 values in a block of 1024
long before = a.copies;
for (int i = 0; i < 10000; i++) { // then append one and remove it, 10,000 times
a.append();
a.removeLast();
}
System.out.println("shrink at " + shrinkAt + ": " + (a.copies - before) + " copies for 20000 operations");
}
}
}
// shrink at 0.5: 20480000 copies for 20000 operations
// shrink at 0.25: 1024 copies for 20000 operationsclass ShrinkingArray { // counts the values a real one would copy
constructor(shrinkAt) { // shrink when it falls to this share of its block: 1/2 or 1/4
this.capacity = 1;
this.size = 0;
this.copies = 0;
this.shrinkAt = shrinkAt;
}
append() {
if (this.size === this.capacity) {
this.capacity *= 2;
this.copies += this.size; // every value moves to the bigger block
}
this.size++;
}
removeLast() {
this.size--;
if (this.capacity > 1 && this.size <= this.capacity * this.shrinkAt) {
this.capacity /= 2;
this.copies += this.size; // every value left moves to the smaller block
}
}
}
for (const shrinkAt of [0.5, 0.25]) {
const a = new ShrinkingArray(shrinkAt);
for (let i = 0; i < 1024; i++) a.append(); // full: 1024 values in a block of 1024
const before = a.copies;
for (let i = 0; i < 10000; i++) { // then append one and remove it, 10,000 times
a.append();
a.removeLast();
}
console.log(`shrink at ${shrinkAt}: ${a.copies - before} copies for 20000 operations`);
}
// shrink at 0.5: 20480000 copies for 20000 operations
// shrink at 0.25: 1024 copies for 20000 operationsShrinking at half copied 20,480,000 values for 20,000 operations, 1,024 per operation: the array's size each time. Shrinking at a quarter copied 1,024 once and nothing after, because after a doubling the block is half full, and it takes many appends or removes to reach full or a quarter again. That gap is where the savings come from: charge 3 and the bank survived every sequence of 18 appends and removes. Shrinking at half has no such charge: the smallest that survived every sequence was 4 for 10 operations, 5 for 14 and 6 for 18, and it keeps rising, because a longer run can grow the array before it starts to thrash.
One operation can still be slow. Amortized O(1) is a promise about the total, not about each operation. Here each of a million appends is timed on its own:
#include <bits/stdc++.h>
using namespace std;
using Clock = chrono::steady_clock;
int main() {
const int n = 1000000;
vector<int> plain;
auto start = Clock::now();
for (int i = 0; i < n; i++) plain.push_back(i);
double average = chrono::duration<double, nano>(Clock::now() - start).count() / n;
vector<int> items;
double slowest = 0;
int at = 0;
for (int i = 0; i < n; i++) {
auto t = Clock::now();
items.push_back(i);
double took = chrono::duration<double, micro>(Clock::now() - t).count();
if (took > slowest) slowest = took, at = i;
}
printf("%zu appends: %.0f ns on average, the slowest %.0f us, at index %d\n", plain.size(), average, slowest,
at);
}
// 1000000 appends: 6 ns on average, the slowest 1660 us, at index 524288import time
n = 1000000
plain = []
start = time.perf_counter()
for i in range(n):
plain.append(i)
average = (time.perf_counter() - start) / n * 1e9
items, slowest, at = [], 0, 0
for i in range(n):
t = time.perf_counter_ns()
items.append(i)
took = time.perf_counter_ns() - t
if took > slowest:
slowest, at = took, i
print(f"{len(plain)} appends: {average:.0f} ns on average, the slowest {slowest / 1000:.0f} us, at index {at}")
# 1000000 appends: 112 ns on average, the slowest 114 us, at index 57952import java.util.*;
public class Main {
public static void main(String[] args) {
int n = 1000000;
List<Integer> plain = new ArrayList<>();
long start = System.nanoTime();
for (int i = 0; i < n; i++) plain.add(i);
double average = (double) (System.nanoTime() - start) / n;
List<Integer> items = new ArrayList<>();
long slowest = 0;
int at = 0;
for (int i = 0; i < n; i++) {
long t = System.nanoTime();
items.add(i);
long took = System.nanoTime() - t;
if (took > slowest) {
slowest = took;
at = i;
}
}
System.out.printf("%d appends: %.0f ns on average, the slowest %d us, at index %d%n", plain.size(), average,
slowest / 1000, at);
}
}
// 1000000 appends: 126 ns on average, the slowest 22822 us, at index 810325const n = 1000000;
const plain = [];
const start = process.hrtime.bigint();
for (let i = 0; i < n; i++) plain.push(i);
const average = Number(process.hrtime.bigint() - start) / n;
const items = [];
let slowest = 0n, at = 0;
for (let i = 0; i < n; i++) {
const t = process.hrtime.bigint();
items.push(i);
const took = process.hrtime.bigint() - t;
if (took > slowest) {
slowest = took;
at = i;
}
}
console.log(`${plain.length} appends: ${average.toFixed(0)} ns on average, the slowest ${slowest / 1000n} us, ` +
`at index ${at}`);
// 1000000 appends: 36 ns on average, the slowest 8270 us, at index 869461In C++ the slowest append was index 524,288: the push that found the vector full and copied 524,288 values, 1,660 µs against 6 ns on average. In every language the slowest append took at least 1,018 times the average (Python's slowest 114 µs, Java's 22,822 µs, JavaScript's 8,270 µs). For a sorting job that doesn't matter. For a game drawing a frame every 16 ms, or a server promising each request in a millisecond, one slow append is the one that counts, and the fix is to reserve the room up front.
Amortized is not average. An average case averages over inputs; amortized averages over the operations of one run and holds for every run, with no randomness. An amortized O(1) append is O(1) per append on the worst sequence you can build.
Where it comes back
- Growing arrays:
vector,ArrayList, Python's list and JavaScript's arrays all append in O(1) amortized; Introduction to Arrays measured their growth. - The monotonic stack and the sliding window: each index enters and leaves once, so the inner loop is O(n) over the whole run.
- A queue made of two stacks: each value is moved from one stack to the other at most once, so each operation is O(1) amortized (Introduction to Queues).
- Hash tables: once a table passes its load limit (one key a bucket for C++'s
unordered_map, three quarters for Java'sHashMap, two thirds for Python'sdict), it is rebuilt at about double the size, the same argument as the growing array. - Union-find: with path compression and union by rank, each operation is O(α(n)) amortized, where α grows so slowly that it stays at 4 or less for any n that fits in memory (the Graphs section builds it).
Mistakes that cost an interview
"A while inside a for is O(n²)." Count each value's pushes and pops over the whole run: the stack above made 2n − 1 steps, though one step popped n − 1.
reserve(size + 1) before every push_back. Meant as an optimisation, in C++ it asks for exactly one more slot, so the vector moves to a new block on every push and the doubling is gone:
#include <bits/stdc++.h>
using namespace std;
void fill(int n, bool reserveFirst) {
auto start = chrono::steady_clock::now();
vector<int> v;
int moves = 0; // how often the vector moved to a new block
size_t capacity = v.capacity();
for (int i = 0; i < n; i++) {
if (reserveFirst) v.reserve(v.size() + 1); // "make room first": exactly one more slot
v.push_back(i);
if (v.capacity() != capacity) capacity = v.capacity(), moves++;
}
double s = chrono::duration<double>(chrono::steady_clock::now() - start).count();
printf("%s, n = %d: moved %d times, %.4fs\n", reserveFirst ? "reserve first" : "push_back alone", n, moves, s);
}
int main() {
for (int n : {10000, 20000, 40000}) fill(n, true);
for (int n : {10000, 20000, 40000}) fill(n, false);
}
// reserve first, n = 10000: moved 10000 times, 0.0062s
// reserve first, n = 20000: moved 20000 times, 0.0341s
// reserve first, n = 40000: moved 40000 times, 0.4761s
// push_back alone, n = 10000: moved 15 times, 0.0001s
// push_back alone, n = 20000: moved 16 times, 0.0001s
// push_back alone, n = 40000: moved 17 times, 0.0002sReserving first moved the vector 40,000 times for 40,000 pushes, copying 1 + 2 + … + 39,999 values, and took 0.48 s: O(n²). Plain push_back moved 17 times and took 200 µs. Reserve once, for the size you'll reach.
Growing by a fixed amount. Adding 10 slots when full makes copies of 10, 20, 30, …, which add up to about n²/20: O(n) per append. Grow by a factor.
Shrinking at the same point you grow. Shrink at a quarter full, not at half.
"Amortized O(1), so every call is fast." One call can be O(n); only the total is promised.
Check yourself
Quiz
1 / 5Multiple choice
nums holds n values. How many steps does this loop take in total?long long count = 0;
vector<int> stack;
for (int x : nums) {
while (!stack.empty() && stack.back() < x) {
stack.pop_back();
count++;
}
stack.push_back(x);
count++;
}Multiple choice
long long count = 0; // values copied
long long capacity = 10, size = 0;
for (int i = 0; i < n; i++) {
if (size == capacity) {
count += size; // move them all
capacity += 10; // to a block 10 bigger
}
size++;
}Multiple choice
Multiple choice
Multiple choice
Practice
Complexity Quiz: Medium and Hard, at the end of this section, include loops whose cost is amortized. To use the idea, the problems of Monotonic Stack: Next Greater and Smaller Elements and Introduction to Sliding Window each need the whole-run count to see why they're O(n). Next: Recurrence Relations and the Master Theorem, the cost of a recursion.