Asymptotics and amortized analysis
list.append is cheap even though one append in a while is slow.After this lesson, you will be able to:
- State the definitions of O, Omega, Theta and little-o using a constant c and a starting size n0, and say what each one promises
- Prove f(n) = O(g(n)) by choosing c and n0, check the choice by running it, and prove that a bound is false
- Order the common growth classes from O(1) to O(n!) and give real step counts for each
- Tell best, worst, average and expected case apart, and say why O is not the same as worst case
- Explain the difference between an upper bound and a lower bound, and prove that finding the maximum needs n - 1 comparisons
- Solve a recurrence by guessing a bound and proving it by induction, and count space including the recursion stack
- Analyse amortized cost with the aggregate, accounting and potential methods, and tell amortized from expected
- Spot the three common analysis mistakes: nested loops that are not n², log n against n log n, and recursion depth taken as time
Before You Start
You have used Big-O for the whole part. Now you will build it from its definition. Every proof here is written in plain words, and every number in it is checked by a cell you can run. The cells check many values. The algebra is what covers all of them.
#Why We Need an Exact Language for Cost
Think of two delivery drivers. One says "my trip never takes more than two hours". The other says "my trip usually takes forty minutes". These are different kinds of claims. The first is a ceiling. The second is a typical value. A manager who mixes them up will promise the wrong delivery time.
Algorithm claims have the same problem. "O(n²)" is a ceiling on growth. "Takes n steps on average" is a typical value. "Always takes at least n steps" is a floor. Words like worst case and average case say which input you mean. Words like O and Omega say which kind of bound you claim. You need both pairs of words, and they are separate.
#O, Omega, Theta and Little-o in Plain Words
f(n) ≤ c * g(n) for every n from n0 on. It is a ceiling: f grows no faster than g, up to a constant.f(n) ≥ c * g(n) for every n from n0 on. It is a floor: f grows at least as fast as g.The cell shows the picture for f(n) = 3n + 10 and g(n) = n. We claim c = 4 and n0 = 10. Look at the table to see where the claim starts to hold.
def f(n):
return 3 * n + 10 # the cost we are measuring
def g(n):
return n # the simple shape we compare it with
c, n0 = 4, 10 # the claim: f(n) <= c * g(n) for every n from n0 on
print("n f(n) c*g(n) f(n) <= c*g(n)?")
for n in (1, 5, 9, 10, 11, 50, 1000):
print(f"{n:<5} {f(n):<6} {c * g(n):<8} {f(n) <= c * g(n)}")
print("holds for every n from", n0, "to 100000:", all(f(n) <= c * g(n) for n in range(n0, 100_001)))
# Output:
# n f(n) c*g(n) f(n) <= c*g(n)?
# 1 13 4 False
# 5 25 20 False
# 9 37 36 False
# 10 40 40 True
# 11 43 44 True
# 50 160 200 True
# 1000 3010 4000 True
# holds for every n from 10 to 100000: TrueAt n = 9 the claim fails, and at n = 10 it holds with nothing to spare. For every size after that, f stays under 4n. So 3n + 10 is O(n). The cell checks 100,000 values, and the next section shows why the algebra covers all of them.
f(n) = 3n + 10. Which statement is true?
f(n) = O(g(n)) is a habit of speech. It really means "f belongs to the family of functions that have this ceiling".#Proving f(n) = O(g(n)) by Choosing c and n0
To prove an O claim, you do not argue about the whole curve. You pick two numbers and show they work. The recipe has four steps.
- Write f and g.
- Choose a constant c. A safe pick is large enough to cover every term of f.
- Solve the inequality
f(n) ≤ c * g(n)for n. The answer tells you n0. - State c and n0, then check them with a few real values.
3n + 10 ≤ 4n. Take away 3n from both sides and the inequality says 10 ≤ n. So it holds for every n from 10 on, and n0 = 10. The cell checks it, and it also shows the claim breaks at n = 9, so n0 cannot be smaller.f = lambda n: 3 * n + 10
print("c = 4, n0 = 10:", all(f(n) <= 4 * n for n in range(10, 100_001)))
print("n = 9 breaks it:", f(9), "is more than", 4 * 9)
# Output:
# c = 4, n0 = 10: True
# n = 9 breaks it: 37 is more than 36For the lower bound, f(n) is 2n² plus positive terms, so f(n) ≥ 2n² for every n from 1 on. That gives c = 2 and n0 = 1. Two bounds, so Θ(n²).
2n² + 5n + 7 ≤ 3n², which says n² ≥ 5n + 7. That first holds at n = 7 (49 against 42) and not at n = 6 (36 against 37). So c = 3 with n0 = 7 works too. A smaller c costs you a larger n0.f = lambda n: 2 * n * n + 5 * n + 7
print("upper, c = 14, n0 = 1:", all(f(n) <= 14 * n * n for n in range(1, 100_001)))
print("lower, c = 2, n0 = 1:", all(f(n) >= 2 * n * n for n in range(1, 100_001)))
print("another pair, c = 3, n0 = 7:", all(f(n) <= 3 * n * n for n in range(7, 100_001)))
print("n = 6 breaks that pair:", f(6), "is more than", 3 * 6 * 6)
# Output:
# upper, c = 14, n0 = 1: True
# lower, c = 2, n0 = 1: True
# another pair, c = 3, n0 = 7: True
# n = 6 breaks that pair: 109 is more than 108n² ≤ c * n for every n from n0 on. Divide both sides by n, which is positive, and we get n ≤ c for every n from n0 on.But take n to be c + 1, or n0 if that is larger. Then n is bigger than c, and the claim breaks. So no such c exists. The cell tries three values of c.
for c in (1, 10, 1000):
n = c + 1
print(f"c = {c}: at n = {n}, n^2 = {n * n} but c * n = {c * n}. Still n^2 <= c * n? {n * n <= c * n}")
# Output:
# c = 1: at n = 2, n^2 = 4 but c * n = 2. Still n^2 <= c * n? False
# c = 10: at n = 11, n^2 = 121 but c * n = 110. Still n^2 <= c * n? False
# c = 1000: at n = 1001, n^2 = 1002001 but c * n = 1001000. Still n^2 <= c * n? FalseFor any c you choose, a slightly larger n beats it. That is what "grows faster" means.
#Why Constants and Lower-Order Terms Drop
Two things get dropped when we write Big-O, and the definition tells us why each is safe.
A constant multiplier is absorbed by c. The functions 3n, 100n and n all have the same shape up to a constant, and c is exactly the room we give ourselves to ignore it. So 100n is O(n) with c = 100.
A lower-order term is a term that grows slower than the biggest one, such as 5n and 7 inside 2n² + 5n + 7. It stops mattering as n grows. The cell shows the share of f(n) that comes from 2n² alone.
for n in (10, 100, 1_000, 100_000):
f = 2 * n * n + 5 * n + 7
print(f"n={n:<8} f(n)={f:<15,} f(n)/n^2={f / (n * n):.4f} 2n^2 is {2 * n * n / f:.2%} of f(n)")
# Output:
# n=10 f(n)=257 f(n)/n^2=2.5700 2n^2 is 77.82% of f(n)
# n=100 f(n)=20,507 f(n)/n^2=2.0507 2n^2 is 97.53% of f(n)
# n=1000 f(n)=2,005,007 f(n)/n^2=2.0050 2n^2 is 99.75% of f(n)
# n=100000 f(n)=20,000,500,007 f(n)/n^2=2.0001 2n^2 is 100.00% of f(n)At n = 10, the squared term is about 78 percent of the cost. At n = 100, it is about 98 percent. By a hundred thousand it is the whole story, and f(n) divided by n² has settled at 2. That is the sense in which Big-O keeps only the part that grows fastest.
One warning belongs here. Dropping constants tells you the shape of the growth. It does not tell you which of two programs is faster today. Section "Practical Reality" comes back to this.
#Growth Classes in Order, with Real Counts
Here are the common classes, from the slowest-growing to the fastest. If f is in a class earlier in the list, it is also O of every class later in the list.
- O(1): a fixed number of steps.
- O(log n): halve the problem each step.
- O(n): touch each value once.
- O(n log n): halve repeatedly and touch everything at each level.
- O(n²) and O(n³): every value against every value, or every triple.
- O(2^n): try every subset of n values.
- O(n!): try every order of n values.
The cell prints real counts for the polynomial classes first, and then for the two that explode.
import math
print(f"{'n':>10} {'log2 n':>7} {'n':>10} {'n log2 n':>12} {'n^2':>16} {'n^3':>20}")
for n in (10, 100, 1_000, 1_000_000):
print(f"{n:>10,} {math.ceil(math.log2(n)):>7} {n:>10,} {round(n * math.log2(n)):>12,} {n ** 2:>16,} {n ** 3:>20,}")
print()
for n in (10, 20, 30, 40, 60):
print(f"n={n}: 2^n = {2 ** n:,}")
for n in (5, 10, 15, 20):
print(f"n={n}: n! = {math.factorial(n):,}")
# Output:
# n log2 n n n log2 n n^2 n^3
# 10 4 10 33 100 1,000
# 100 7 100 664 10,000 1,000,000
# 1,000 10 1,000 9,966 1,000,000 1,000,000,000
# 1,000,000 20 1,000,000 19,931,569 1,000,000,000,000 1,000,000,000,000,000,000
#
# n=10: 2^n = 1,024
# n=20: 2^n = 1,048,576
# n=30: 2^n = 1,073,741,824
# n=40: 2^n = 1,099,511,627,776
# n=60: 2^n = 1,152,921,504,606,846,976
# n=5: n! = 120
# n=10: n! = 3,628,800
# n=15: n! = 1,307,674,368,000
# n=20: n! = 2,432,902,008,176,640,000Read the last row of the first table. A million values cost 20 steps in log n, a million in n, about 20 million in n log n, a million million in n². The second table is the reason exponential and factorial algorithms are used only when n is tiny. At n = 60, 2^n is already about a million million million.
#Best, Worst, Average and Expected Case
A cost is a function of n, but on the same n, different inputs cost different amounts. So we need words that say which input we mean.
Notice that these words pick a function, and O, Omega and Theta describe a function. They are two separate choices. For one algorithm you can say: the worst case is Θ(n²), the best case is Θ(n). You can even say that the cost is O(n²) for every input.
Before you run the cell, predict one thing. A list has 100 different values. We search for a target that is equally likely to sit at any position.
Linear search reads the values from the front and stops when it finds the target. The list has 100 different values, and the target is equally likely to be at any position. On average, how many values does it read?
def linear_search_steps(items, target):
steps = 0
for x in items:
steps += 1
if x == target:
break
return steps
n = 100
items = list(range(n))
all_steps = [linear_search_steps(items, t) for t in items] # one search for every possible position
print("best case:", min(all_steps))
print("worst case:", max(all_steps))
print("average over all positions:", sum(all_steps) / n)
def insertion_comparisons(a):
a = a[:]
count = 0
for i in range(1, len(a)):
j = i
while j > 0:
count += 1
if a[j - 1] <= a[j]:
break
a[j - 1], a[j] = a[j], a[j - 1]
j -= 1
return count
print("insertion sort comparisons: n, already sorted, reversed")
for n in (10, 100, 1000):
print(n, insertion_comparisons(list(range(n))), insertion_comparisons(list(range(n, 0, -1))))
# Output:
# best case: 1
# worst case: 100
# average over all positions: 50.5
# insertion sort comparisons: n, already sorted, reversed
# 10 9 45
# 100 99 4950
# 1000 999 499500The linear search gives 1, 100 and 50.5. The second part counts insertion sort. Already sorted, it makes n - 1 comparisons, and reversed it makes n(n - 1)/2. Both are real, exact counts. So insertion sort has a best case of Θ(n) and a worst case of Θ(n²), and calling it just "O(n²)" is true but hides the first half.
A common slip says "O means worst case". It does not. O is a ceiling on a function. Worst case chooses which function. You can put a Θ on the worst case, or an O on the best case.
#Upper Bounds and Lower Bounds
Call a value a loser once it has lost at least one comparison, meaning some other value was found to be bigger. Every value except the real maximum must be a loser by the end. If one of them had never lost, the algorithm would have no evidence that it is smaller than the answer it gave. An unlucky input could make it the biggest, and the algorithm would be wrong.
A single comparison creates at most one new loser. So n - 1 losers need at least n - 1 comparisons.
The upper bound and the lower bound meet at n - 1, so the problem is Θ(n), and the scan is the best possible.
For sorting the argument goes through counting. There are n! possible orders of n different values. Each comparison is a yes or no question, so k comparisons can tell apart at most 2^k orders. We need 2^k ≥ n!, so k ≥ log2(n!). The last n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^(n/2), which makes log2(n!) at least (n/2) log2(n/2). That grows like n log n. The cell prints the exact numbers.
import math
def find_max(items):
comparisons = 0
best = items[0]
for x in items[1:]:
comparisons += 1
if x > best:
best = x
return best, comparisons
for n in (2, 10, 1000):
print(f"n={n}: scan comparisons {find_max(list(range(n)))[1]}, lower bound {n - 1}")
for n in (3, 4, 5, 10, 20):
orders = math.factorial(n)
need = math.ceil(math.log2(orders))
print(f"sorting n={n}: {orders:,} possible orders, so at least {need} yes/no comparisons")
# Output:
# n=2: scan comparisons 1, lower bound 1
# n=10: scan comparisons 9, lower bound 9
# n=1000: scan comparisons 999, lower bound 999
# sorting n=3: 6 possible orders, so at least 3 yes/no comparisons
# sorting n=4: 24 possible orders, so at least 5 yes/no comparisons
# sorting n=5: 120 possible orders, so at least 7 yes/no comparisons
# sorting n=10: 3,628,800 possible orders, so at least 22 yes/no comparisons
# sorting n=20: 2,432,902,008,176,640,000 possible orders, so at least 62 yes/no comparisonsSorting five values needs at least 7 comparisons, since 2^6 = 64 is below 120 and 2^7 = 128 is above. Twenty values need at least 62. The Sorting Algorithms lesson uses this result, and this proof is where it comes from.
Be honest about the gap in practice. For most problems nobody knows a matching pair of bounds. Between the best known algorithm and the best known lower bound there is often a gap. A claim like "this cannot be done faster" is a lower bound, and it needs a proof of its own.
#Solving Recurrences by Substitution
T(n) = 2T(n/2) + n, with T(1) = 1.T(n) ≤ c * n * log2(n). Test the first case. At n = 1 the right side is 0 and T(1) is 1, so the guess fails there. That is a real trap, and it is why we start the induction at n = 2.4 ≤ c * 2 * 1, so c = 2 works.Now the step. Suppose T(m) ≤ 2m log2(m) for every power of 2 from 2 up to n/2, and n ≥ 4. Then T(n) = 2T(n/2) + n ≤ 2 · 2(n/2) log2(n/2) + n = 2n(log2 n - 1) + n = 2n log2 n - n, which is at most 2n log2 n. The guess holds, so T(n) is O(n log n).
We proved it only for powers of 2. The general case also holds, but it needs rounding up and down, which this lesson skips on purpose.
T(n) ≤ c * n. The step gives c * n + n, which is more than c * n for every c. The guess is too low. The cell shows the numbers: T(n) divided by n keeps rising, 2, 3, 4, and so on.def T(n):
"""T(1) = 1 and T(n) = 2 T(n/2) + n, for n a power of 2."""
return 1 if n == 1 else 2 * T(n // 2) + n
print(f"{'n':>6} {'T(n)':>8} {'n log2 n':>9} {'2 n log2 n':>11} {'T(n) <= 2 n log2 n':>19} {'T(n)/n':>7}")
for k in range(1, 11):
n = 2 ** k
print(f"{n:>6} {T(n):>8} {n * k:>9} {2 * n * k:>11} {str(T(n) <= 2 * n * k):>19} {T(n) / n:>7.1f}")
print("T(n) = n log2 n + n for every power of 2 up to 2^14:", all(T(2 ** k) == 2 ** k * k + 2 ** k for k in range(15)))
print("at n = 1: T(1) =", T(1), "but 2 * 1 * log2(1) =", 0, "so the guess fails there")
def S(n):
"""S(1) = 1 and S(n) = S(n - 1) + n."""
return 1 if n == 1 else S(n - 1) + n
print("S(n) <= n^2 for n up to 199:", all(S(n) <= n * n for n in range(1, 200)), "| S(10) =", S(10))
# Output:
# n T(n) n log2 n 2 n log2 n T(n) <= 2 n log2 n T(n)/n
# 2 4 2 4 True 2.0
# 4 12 8 16 True 3.0
# 8 32 24 48 True 4.0
# 16 80 64 128 True 5.0
# 32 192 160 320 True 6.0
# 64 448 384 768 True 7.0
# 128 1024 896 1792 True 8.0
# 256 2304 2048 4096 True 9.0
# 512 5120 4608 9216 True 10.0
# 1024 11264 10240 20480 True 11.0
# T(n) = n log2 n + n for every power of 2 up to 2^14: True
# at n = 1: T(1) = 1 but 2 * 1 * log2(1) = 0 so the guess fails there
# S(n) <= n^2 for n up to 199: True | S(10) = 55#Space Complexity
The recursion stack counts as space. Each call that has not returned yet holds a frame, which is a block of memory that stores its variables. A recursion that goes n calls deep uses n frames. This is the part beginners forget.
def sum_loop(items):
total = 0 # one extra variable: O(1) extra space
for x in items:
total += x
return total
depth = 0
deepest = 0
def sum_recursive(items, i=0):
"""Adds items[i:] by calling itself. Every call waits on the stack."""
global depth, deepest
depth += 1
deepest = max(deepest, depth)
result = 0 if i == len(items) else items[i] + sum_recursive(items, i + 1)
depth -= 1
return result
def halving_depth(n):
"""How deep does a recursion go when each call halves the input?"""
return 1 if n <= 1 else 1 + halving_depth(n // 2)
for n in (10, 100, 500):
depth = deepest = 0
total = sum_recursive(list(range(n)))
print(f"n={n}: same answer {total == sum_loop(list(range(n)))}, loop extra cells 1, recursive stack depth {deepest}")
for n in (1000, 1_000_000, 1_000_000_000):
print(f"n={n:,}: halving recursion depth {halving_depth(n)}")
# Output:
# n=10: same answer True, loop extra cells 1, recursive stack depth 11
# n=100: same answer True, loop extra cells 1, recursive stack depth 101
# n=500: same answer True, loop extra cells 1, recursive stack depth 501
# n=1,000: halving recursion depth 10
# n=1,000,000: halving recursion depth 20
# n=1,000,000,000: halving recursion depth 30The loop sums n values with one extra cell, O(1). The recursive version gets the same answer but holds n + 1 frames at its deepest, O(n) space. A recursion that halves its input is only about 30 deep, even for a billion values. In CPython the default limit is about a thousand nested calls, so the recursive sum above would stop with an error near n = 1,000.
The rest of the common cases are short to list. Merge sort uses O(n) extra space for its merged lists. An in-place quick sort uses only its stack, which is about log n deep for a random pivot. A hash set that remembers n values costs O(n) space, and buys O(1) lookups in return.
Space matters in real systems. A table of the distance between every pair of n points has n² cells. For 100,000 points that is ten billion cells, and at 8 bytes each it is about 80 gigabytes. The time may be fine and the memory still the wall.
#Amortized Analysis: The Idea
list.append writes one value, but when the list is full it must copy every value into a bigger block. If you judged by that single slow append, you would call append O(n). If you judged only by the fast ones, you would miss the copy.There are three standard methods for finding the amortized cost. They always give the same answer, and each fits a different problem. We use all three.
#The Aggregate Method: The Dynamic Array
A dynamic array starts with room for 1 value. When it is full, it makes a block twice as big and copies every value across. Each append costs 1 step for the write. The cell counts the copies, step by step.
A dynamic array starts with room for 1 value and doubles its room whenever it is full. Each copy of one value counts as one step. After 1,000 appends, about how many values have been copied in total?
class DynamicArray:
"""A growing array that doubles its capacity when it is full, and counts every copy."""
def __init__(self):
self.capacity = 1
self.size = 0
self.copies = 0
def append(self):
if self.size == self.capacity:
self.copies += self.size # copy every value into the bigger block
self.capacity *= 2
self.size += 1 # write the new value (1 step)
for n in (10, 100, 1000, 100_000):
arr = DynamicArray()
for _ in range(n):
arr.append()
total = n + arr.copies
print(f"n={n:<7} copies={arr.copies:<7} total steps={total:<8} per append={total / n:.3f}")
class StepArray:
"""The same idea, but it grows by a fixed 10 cells each time."""
def __init__(self):
self.capacity = 1
self.size = 0
self.copies = 0
def append(self):
if self.size == self.capacity:
self.copies += self.size
self.capacity += 10
self.size += 1
for n in (1000, 10_000):
arr = StepArray()
for _ in range(n):
arr.append()
print(f"grow by 10: n={n:<6} copies={arr.copies:<9} per append={(n + arr.copies) / n:.1f}")
# Output:
# n=10 copies=15 total steps=25 per append=2.500
# n=100 copies=127 total steps=227 per append=2.270
# n=1000 copies=1023 total steps=2023 per append=2.023
# n=100000 copies=131071 total steps=231071 per append=2.311
# grow by 10: n=1000 copies=49600 per append=50.6
# grow by 10: n=10000 copies=4996000 per append=500.6For 1,000 appends the total is 2,023 steps, about 2 per append. Here is the proof for any n. Writes cost n. The copies happen at sizes 1, 2, 4, and so on up to p, the largest power of 2 below n. That sum is 2p - 1, and p is less than n, so the copies total less than 2n.
The overall cost is less than 3n, so the amortized cost per append is under 3, which is O(1).
Now look at the second half of the cell. The array that grows by a fixed 10 cells copies about n² / 20 values, and the cost per append climbs with n. Growing by a fixed amount gives O(n) amortized per append, and growing by a fixed ratio gives O(1).
Real CPython lists grow by a bit more than an eighth each time, not by double. The same proof works for any fixed ratio above 1. The constant changes, and the O(1) does not.
#The Accounting Method
The rule is simple: the bank must never go below zero. If it never does, the total real cost is at most the total charged, and the charge is a valid amortized cost.
For the dynamic array, try a charge of 3 coins per append. One coin pays for the write. Two coins are saved with the new value. When the array is full at size k and doubles, it copies k values. Since the last doubling, k/2 values have been added, and each saved 2 coins. That is k coins in the bank, exactly enough for the copy.
Does a charge of 2 work? It saves 1 coin per append, so only k/2 coins sit in the bank when k are needed. The cell tracks the bank for all three charges.
def lowest_balance(charge, n):
"""Charge `charge` coins per append. Pay 1 coin per write and 1 coin per copied value."""
capacity, size, bank, lowest = 1, 0, 0, 0
for _ in range(n):
bank += charge
if size == capacity:
bank -= size # pay for copying every value
capacity *= 2
bank -= 1 # pay for the write
size += 1
lowest = min(lowest, bank)
return lowest
for charge in (2, 3, 4):
print(f"charge {charge} per append: lowest balance over 5000 appends = {lowest_balance(charge, 5000)}")
# Output:
# charge 2 per append: lowest balance over 5000 appends = -4094
# charge 3 per append: lowest balance over 5000 appends = 0
# charge 4 per append: lowest balance over 5000 appends = 0A charge of 2 drives the bank far below zero, so it fails. A charge of 3 never goes below zero, so it is a valid amortized cost. That matches the aggregate method, which gave a bound under 3. The accounting method gave a tidy story about why: every value pays for its own future copy.
#The Potential Method
amortized cost = actual cost + (potential after) - (potential before).Add this up over a whole sequence. The potential terms cancel in pairs, and what is left is the total actual cost plus the final potential minus the starting potential. The final potential is not negative and the start is 0, so the total amortized cost is at least the total actual cost.
If you can show each amortized cost is small, you have bounded the total. Choosing Φ is the hard part. A good Φ goes up when you save for future work and goes down when you spend it.
A binary counter starts at 0 and is incremented 1,000 times. Each flip of a bit from 0 to 1 or from 1 to 0 counts as one step. About how many flips happen in total?
Now let the potential be the number of 1 bits. If an increment flips t trailing ones to zero and one zero to one, the actual cost is t + 1. The number of ones changes by 1 - t. So the amortized cost is (t + 1) + (1 - t) = 2, whatever t is.
def increment(bits):
"""Add 1 to a binary counter stored as a list of bits, lowest bit first. Returns the bit flips."""
flips = 0
i = 0
while i < len(bits) and bits[i] == 1:
bits[i] = 0 # a 1 turns into 0 and the carry moves on
flips += 1
i += 1
if i == len(bits):
bits.append(0)
bits[i] = 1 # the first 0 turns into 1, and the carry stops
flips += 1
return flips
bits = []
total = 0
always_two = True
for n in range(1, 1001):
before = sum(bits) # the potential before: the number of 1 bits
flips = increment(bits)
after = sum(bits)
amortized = flips + (after - before) # actual cost plus the change in potential
always_two = always_two and amortized == 2
total += flips
if n in (1, 2, 3, 4, 7, 8, 1000):
print(f"increment {n:>4}: flips={flips} ones before={before} after={after} amortized={amortized}")
print("amortized cost was 2 on every increment:", always_two)
print("total flips for 1000 increments:", total, "| 2n - (ones in 1000) =", 2000 - bin(1000).count("1"))
# Output:
# increment 1: flips=1 ones before=0 after=1 amortized=2
# increment 2: flips=2 ones before=1 after=1 amortized=2
# increment 3: flips=1 ones before=1 after=2 amortized=2
# increment 4: flips=3 ones before=2 after=1 amortized=2
# increment 7: flips=1 ones before=2 after=3 amortized=2
# increment 8: flips=4 ones before=3 after=1 amortized=2
# increment 1000: flips=4 ones before=8 after=6 amortized=2
# amortized cost was 2 on every increment: True
# total flips for 1000 increments: 1994 | 2n - (ones in 1000) = 1994Every one of the 1,000 increments has amortized cost exactly 2, though one of them flips 4 bits and another flips 1. The total cost of n increments is below 2n. The aggregate view agrees: bit 0 flips every increment, bit 1 every second one, bit 2 every fourth one, so n increments flip about n + n/2 + n/4 + ... bits, which is under 2n.
#Two More Worked Examples: Multipop and Union-Find
push, and multipop(k) which removes up to k values. One multipop can cost k steps, so a careless bound for n operations is n times n. The aggregate argument is better. Each value is pushed once, and it can be popped at most once. So the total number of pops is at most the number of pushes, and n operations cost at most 2n steps in total.The potential method says the same: let Φ be the stack size. A push costs 1 and raises Φ by 1, so its amortized cost is 2. A multipop of k' values costs k' and lowers Φ by k', so its amortized cost is 0.
def run(ops):
"""Each op is ('push', value) or ('multipop', k). Returns (steps, pushes, pops)."""
stack, steps, pushes, pops = [], 0, 0, 0
for op, arg in ops:
if op == "push":
stack.append(arg)
steps += 1
pushes += 1
else:
k = 0
while stack and k < arg: # pop up to arg values, one step each
stack.pop()
steps += 1
pops += 1
k += 1
return steps, pushes, pops
ops = []
for i in range(1, 2001):
ops.append(("push", i))
if i % 100 == 0:
ops.append(("multipop", 20)) # now and then, a costly operation
if i % 7 == 0:
ops.append(("multipop", 3))
steps, pushes, pops = run(ops)
print("operations:", len(ops), "| pushes:", pushes, "| pops:", pops, "| total steps:", steps)
print("steps per operation:", round(steps / len(ops), 3))
print("pops <= pushes:", pops <= pushes, "| steps <= 2 * pushes:", steps <= 2 * pushes)
# Output:
# operations: 2305 | pushes: 2000 | pops: 1255 | total steps: 3255
# steps per operation: 1.412
# pops <= pushes: True | steps <= 2 * pushes: TrueThe run has 2,305 operations and only 3,255 steps, about 1.4 per operation, though a single multipop cost up to 20 steps. The bound that pops never exceed pushes holds, as the proof says.
#Expected Versus Amortized
Both words say "average", and they mean different things. This is the question interviewers ask most often.
Amortized is deterministic. There is no randomness. The bound holds for every sequence of operations, and it says that the total over the sequence is small, though one operation may be slow. If you run the same sequence twice, you get the same cost.
Expected comes from probability. The algorithm makes random choices, or the data is assumed random, and the bound is the average over those choices. One run can be unlucky. The bound says it rarely is, and does not promise it never is.
A hash table shows both. Looking up a key is O(1) expected, if the hash function spreads keys out. That is an expectation. Growing the table when it fills is O(1) amortized, as with the dynamic array. Insertion is both: expected amortized O(1).
Randomized quick sort shows the expected kind. If the pivot is always the first value, a sorted input is the worst case. If the pivot is random, no input is bad in advance, and the average over the algorithm's own coin flips is O(n log n). The cell uses a small repeatable random source so the numbers are the same every time you run it.
import math
class Lcg:
"""A tiny repeatable random source, so every run prints the same numbers."""
def __init__(self, seed):
self.state = seed
def below(self, k):
self.state = (self.state * 1103515245 + 12345) % (2 ** 31)
return (self.state >> 8) % k
def quicksort_comparisons(items, pick):
"""Count the comparisons quick sort makes. pick(lo, hi) chooses the pivot's index."""
a = items[:]
count = 0
stack = [(0, len(a) - 1)]
while stack:
lo, hi = stack.pop()
if lo >= hi:
continue
p = pick(lo, hi)
a[lo], a[p] = a[p], a[lo]
pivot, i = a[lo], lo
for j in range(lo + 1, hi + 1):
count += 1
if a[j] < pivot:
i += 1
a[i], a[j] = a[j], a[i]
a[lo], a[i] = a[i], a[lo]
stack.append((lo, i - 1))
stack.append((i + 1, hi))
return count
n = 1000
already_sorted = list(range(n))
fixed = quicksort_comparisons(already_sorted, lambda lo, hi: lo)
print("first value as pivot, sorted input:", fixed, "| n(n-1)/2 =", n * (n - 1) // 2)
rng = Lcg(2024)
runs = [quicksort_comparisons(already_sorted, lambda lo, hi: lo + rng.below(hi - lo + 1)) for _ in range(200)]
print("random pivot, the same sorted input, 200 runs:")
print(" smallest", min(runs), "| average", round(sum(runs) / len(runs)), "| largest", max(runs))
print(" 2 n ln n =", round(2 * n * math.log(n)), "| n^2 / 2 =", n * n // 2)
# Output:
# first value as pivot, sorted input: 499500 | n(n-1)/2 = 499500
# random pivot, the same sorted input, 200 runs:
# smallest 9786 | average 10964 | largest 13728
# 2 n ln n = 13816 | n^2 / 2 = 500000On a sorted list of 1,000 values, a fixed first-value pivot makes 499,500 comparisons. The random pivot averaged 10,964 over 200 runs. Its unluckiest run still made only 13,728. A quadratic run is possible, since a random pivot could pick the smallest value every time, but its chance is tiny.
#Practical Reality: Constants, Cache and Python
Big-O says what happens as n grows without limit. Real inputs have a size, and three things that Big-O hides can decide the winner.
First, constants. Suppose algorithm A takes n log n steps but each step is a hundred times dearer than a step of algorithm B, which takes n² steps. The weights below are made up to show the idea, and the counts are exact.
import math
# Suppose a step of algorithm A costs 100 units and a step of algorithm B costs 1 unit.
# A takes n log2 n steps and B takes n * n steps. These weights are made up to show the idea.
print("n A = 100 * n * log2(n) B = n * n cheaper")
for n in (16, 64, 256, 512, 1024, 2048, 100_000):
a, b = round(100 * n * math.log2(n)), n * n
print(f"{n:<8} {a:<25,} {b:<15,} {'A' if a < b else 'B'}")
n = 2
while 100 * n * math.log2(n) >= n * n:
n += 1
print("A is cheaper from n =", n, "on; checked every n up to 100000:", all(100 * m * math.log2(m) < m * m for m in range(n, 100_001)))
# Output:
# n A = 100 * n * log2(n) B = n * n cheaper
# 16 6,400 256 B
# 64 38,400 4,096 B
# 256 204,800 65,536 B
# 512 460,800 262,144 B
# 1024 1,024,000 1,048,576 A
# 2048 2,252,800 4,194,304 A
# 100000 166,096,405 10,000,000,000 A
# A is cheaper from n = 997 on; checked every n up to 100000: TrueB is cheaper at 512 values, A is cheaper at 1,024, and the crossover is at n = 997. Below that point the "worse" algorithm wins. This is why Python's sort uses insertion sort on short runs inside its n log n method.
Second, memory layout. A list stores its references next to each other in memory, so scanning it moves through memory in order, and a computer is very good at that. A structure that follows a pointer from one scattered node to another is often slower even at the same Big-O. This is called cache behaviour, and it is a hardware fact. Big-O has no term for it.
Third, Python itself. A step in a Python loop is much dearer than a step inside a built-in written in C. The cell counts how many lines of Python run, which is the same on every machine, and not seconds.
import sys
def python_lines_run(func, *args):
"""Count how many lines of Python the interpreter runs inside func."""
lines = 0
def tracer(frame, event, arg):
nonlocal lines
if event == "line":
lines += 1
return tracer
sys.settrace(tracer)
try:
func(*args)
finally:
sys.settrace(None)
return lines
def total_with_loop(items):
total = 0
for x in items:
total += x
return total
def total_with_sum(items):
return sum(items)
for n in (10, 100, 1000):
data = list(range(n))
print(f"n={n}: loop runs {python_lines_run(total_with_loop, data)} lines, sum() runs {python_lines_run(total_with_sum, data)} line")
# Output:
# n=10: loop runs 23 lines, sum() runs 1 line
# n=100: loop runs 203 lines, sum() runs 1 line
# n=1000: loop runs 2003 lines, sum() runs 1 linesum runs one line, because its loop is inside C. So the rule is: use Big-O to choose the algorithm, use built-ins to cut the constant, and measure when two choices are close.#Common Mistakes
#Try It
Here is the five-problem ladder, easy to hard. Each problem gives you code to analyse, and the answer is a count you can check by running. Fill in each TODO and run. Everything printed is a step count, so it is the same every time.
Tests · Problem 1 prints [110, 420] twice and Theta(n^2); problem 2 prints [7, 63, 1023] twice and Theta(n); problem 3 prints 7; problem 4 prints 1000 1023 True and 10000 16383 True; problem 5 prints first dequeue cost 2001, total steps 4000, per value 4.0.
#Recap
O is a ceiling, Omega is a floor and Theta is both, and each is a promise about a function: from some size n0 on, f stays under, over or between constant multiples of g. To prove an O claim, choose c, solve for n0, and check. To disprove it, show that any c is beaten by a larger n. Constants and lower-order terms drop because c absorbs the first and the biggest term swamps the rest.
Best, worst, average and expected case choose which function to bound, and O, Omega and Theta describe it. Upper bounds come from building an algorithm, and lower bounds from arguing about every algorithm, as with n - 1 for the maximum and log2(n!) for sorting.
Recurrences yield to guess and induction. Space counts extra cells and the recursion stack. Amortized analysis bounds the total over any sequence, by aggregate, accounting or potential, and it uses no randomness, while expected cost does. Last, constants, cache and Python overhead can beat a better Big-O at modest n.
Which of these is true for f(n) = 3n + 10?
Key Takeaways
- O is a ceiling, Omega is a floor and Theta is both: from some size n0 on, f stays under, over or between constant multiples of g
- To prove f = O(g), choose c, solve the inequality for n0 and check; to disprove it, show that any c is beaten by a larger n
- Constants are absorbed by c and lower-order terms are swamped by the biggest term, which is why Big-O keeps only the fastest-growing part
- Best, worst, average and expected case pick which function you bound; O, Omega and Theta describe it, so O is not the same as worst case
- Upper bounds come from building an algorithm and lower bounds from arguing about all algorithms, such as n - 1 comparisons for the maximum
- Amortized cost is a guarantee on the total over any sequence of operations, shown by the aggregate, accounting or potential method, and it uses no randomness
- Depth is not time and nested loops are not always n²: count how often each loop really runs and what each level costs