Two correct programs
A national examinations board has a million candidate records and must check that no two candidates were given the same ID. Here are two correct ways to do it in Python:
def has_duplicate_pairs(ids):
n = len(ids)
for i in range(n):
for j in range(i + 1, n):
if ids[i] == ids[j]:
return True
return False
def has_duplicate_set(ids):
seen = set()
for x in ids:
if x in seen:
return True
seen.add(x)
return FalseBoth are always right. But when there are no duplicates, the first compares every pair: comparisons, about for . Even at a hundred million comparisons a second that is well over an hour, and Python is slower. The second does one set lookup and one insertion per record and finishes in well under a second.
Correctness is not enough: an answer that arrives next week is, for most purposes, no answer. This lesson gives you the tools to predict a program's cost before running it, to compare algorithms independently of the machine, and to check predictions by experiment. Every later lesson uses them.
Count steps, not seconds
Why not just time programs? Because seconds depend on the processor, the language, the Python version and what else the computer is doing, so a measurement on one laptop says little about a phone or a server.
Instead, we count steps: simple operations such as an arithmetic operation, a comparison, an assignment, reading xs[i], or calling a function. Each takes at most some fixed amount of time on a given machine, so if we know how the number of steps grows with the input, we know how the time grows, up to a constant factor that depends on the machine. This idealised machine, in which every simple operation costs one unit, is called the cost model (formally, a random-access machine, or RAM).
We then make two simplifications, both deliberate:
- We describe cost as a function of the input size : the length of a list, the number of records, the number of digits.
- We care about growth, not constants. The difference between and steps can be erased by a faster machine or a better compiler; the difference between and cannot, once is large.
Analogy, not a formal construction
To compare walking with driving for a long journey, you don't care that the driver spends a minute finding the car keys. What matters is how the journey time grows with distance: one hour per 5 km versus one hour per 80 km. The key-finding is a constant; the speed is the growth rate. Asymptotic analysis is the habit of ignoring the keys.
Running time and the three notations
Definition— running time
For an algorithm , let be the number of steps takes on input . Its worst-case running time is , and its best-case running time is the corresponding minimum. Its average-case running time is the expected value of when inputs of size are drawn from a stated probability distribution.
Running times are functions from input sizes to step counts. To compare such functions while ignoring constant factors and small inputs, we use three notations. Throughout, and are functions from the natural numbers to the non-negative reals.
Definition— O, Ω and Θ
- (" is big-O of ") if there are constants and such that for all . It says grows at most as fast as .
- ("big-Omega") if there are constants and such that for all . It says grows at least as fast as .
- ("big-Theta") if both hold: and . It says and grow at the same rate, up to constant factors.
The "=" here is a traditional abuse of notation: is really a set of functions, and means . That is why we never write , and why and do not imply .
Two more pieces of vocabulary are useful. We write ("little-o") when : grows strictly slower than . And the definitions give a handy test:
Theorem— The limit test
Suppose exists (possibly ). If , then . If , then but . If , then but .
Proof
If , then by the definition of a limit there is an with for all , so witnesses and witnesses . If , then for large , giving with ; and for any proposed , eventually , so no can witness . The case is symmetric.
∎
Proving bounds
To prove an or bound from the definition, you exhibit the constants. Any constants that work will do; there is no need to find the best ones.
Theorem— A quadratic
.
Proof
Upper bound: for we have and , so . Take , . Lower bound: for all , . Take , .
∎
The same argument shows that any polynomial with is : the leading term dominates, and the lower-order terms only affect the constants. This is why we write and not .
Theorem— Logarithm bases do not matter
For any constants , .
Proof
By the change-of-base formula, , and is a positive constant. So is a constant multiple of , which is by definition.
∎
So we simply write . (In computer science, an unmarked often means , because halving is everywhere; for asymptotics it doesn't matter.)
Theorem— Polynomials are beaten by exponentials
For every fixed , . In particular .
Proof
Take logarithms: . Since (see Exponential and logarithmic functions), we have , so . By the limit test, but not , which also rules out .
∎
In practice you rarely go back to the definitions, because a few rules cover most cases:
- Constant factors vanish: for any constant .
- Sums are dominated by their largest term: . Doing a step and then a step costs .
- Products multiply: a loop that runs times with a body costing costs , provided the body's cost doesn't vary too much between iterations (if it does, add up the iterations exactly, as below).
- Transitivity: if and then ; the same for and .
The common growth rates
A handful of growth rates appear again and again. Here they are, slowest-growing first, with typical sources:
| Growth | Name | Typical source |
|---|---|---|
| constant | reading xs[i]; a dictionary lookup (on average) | |
| logarithmic | halving the problem each step: binary search | |
| linear | one pass over the data | |
| linearithmic | good sorting algorithms; divide and conquer | |
| quadratic | all pairs: the nested loop above | |
| cubic | all triples; the textbook matrix multiplication | |
| exponential | trying every subset | |
| factorial | trying every ordering |
Numbers make the differences vivid. Suppose a machine does simple steps per second, a fair order of magnitude for compiled code (Python is typically ten to a hundred times slower per step). Then, roughly:
| Growth | Steps for | Steps for | Largest in about one second |
|---|---|---|---|
| 10 | 20 | astronomically large | |
| about | |||
| about 460 | |||
| about | (hopeless) | about 26 |
Look at the last column from the other side. If you buy a computer 100 times faster, a linear algorithm handles inputs 100 times bigger, a quadratic one only 10 times bigger, and an exponential one only about 7 more items, since . Better hardware helps good algorithms most. The divide between polynomial growth () and exponential growth is the starting point of complexity theory, which asks which problems have polynomial-time algorithms at all; see Computational complexity in Lumenary Math and Hard problems later in this course.
Counting steps in code
Most running-time analysis comes down to a few loop patterns. In each, count how many times the innermost statement runs, as an exact sum where you can, then simplify.
One loop over the data. for x in xs: with a constant-cost body runs times: .
Two independent nested loops. for i in range(n): for j in range(n): runs the inner body times: .
A triangular loop. When the inner loop starts after the outer index, as in has_duplicate_pairs, the inner body runs times:
Half the work of the full square, but the same growth rate: constants don't change the class.
A halving loop. while n > 1: n = n // 2 runs times, because after iterations has been divided by about , and the loop stops once exceeds . So . Doubling loops (j = 1; while j < n: j *= 2) are logarithmic for the same reason.
A loop inside a halving loop, or the reverse. for i in range(n): around a doubling while loop costs .
The program below counts the steps of each pattern and compares them with the formulas.
import math
def steps_square(n):
steps = 0
for i in range(n):
for j in range(n):
steps += 1
return steps
def steps_triangle(n):
steps = 0
for i in range(n):
for j in range(i + 1, n):
steps += 1
return steps
def steps_halving(n):
steps = 0
while n > 1:
n = n // 2
steps += 1
return steps
def steps_n_log_n(n):
steps = 0
for i in range(n):
j = 1
while j < n:
j *= 2
steps += 1
return steps
print(f"{'n':>5} {'square':>8} {'triangle':>9} {'n(n-1)/2':>9} {'halving':>8} {'floor(log2 n)':>14} {'n log':>7}")
for n in [8, 100, 1000]:
print(f"{n:>5} {steps_square(n):>8} {steps_triangle(n):>9} {n * (n - 1) // 2:>9}"
f" {steps_halving(n):>8} {math.floor(math.log2(n)):>14} {steps_n_log_n(n):>7}")Hidden loops
A single line of Python can hide a loop, and the analysis must count it. Typical costs in CPython, the standard Python implementation:
| Operation | Cost |
|---|---|
xs[i], xs[i] = v, len(xs) | |
xs.append(v), xs.pop() | amortised (see below) |
xs.insert(0, v), xs.pop(0) | : every item shifts along |
v in xs, xs.index(v), xs.count(v) | : a search through the list |
xs[a:b], xs.copy() | , : a copy is made |
v in s, s.add(v) for a set; d[k] for a dict | on average |
sorted(xs), xs.sort() | worst case |
So a loop that does if v in xs: on a list inside a for over items is quadratic, even though it looks like a single loop. That one hidden cost is the entire difference between the two duplicate checkers at the start of the lesson.
Best, worst and average case
Consider linear search: look through a list from the front until you find a target .
- Best case: is first. One comparison: .
- Worst case: is last or absent. comparisons: .
- Average case: if is present and equally likely to be at each of the positions, the expected number of comparisons is , which is .
Notice that there are two independent choices here. The case (best, worst, average) chooses which function we are describing. The notation (, , ) chooses what kind of bound we state about that function. "The worst-case running time of linear search is " and "its best-case running time is " are both precise, true statements. "Linear search is " is also true, since every case is at most linear, but it is a weaker statement.
Engineers usually quote the worst case, because it is a guarantee that no input, however unlucky or malicious, does worse. Average-case statements are only as good as their assumption about the inputs, which real data (already sorted, or crafted by an attacker) often breaks. The amortised cost, next, is a worst-case guarantee about sequences of operations.
Amortised cost: why append is cheap
A Python list stores references to its items in one contiguous block of memory, so that xs[i] can be found by arithmetic in one step. But then what happens when you append to a list whose block is full? A new, bigger block must be allocated and every existing reference copied across. That single append costs . If that happened on every append, building a list of items would cost .
The trick, used by Python's lists, Java's ArrayList, C++'s std::vector and many others, is to over-allocate: when the block is full, grow its capacity by a constant factor, not by a constant amount. Then expensive appends become rarer and rarer as the list grows.
Definition— amortised cost
An operation has amortised cost if, starting from an empty structure, every sequence of such operations costs at most in total, in the worst case. Individual operations may be expensive, as long as they are rare enough to be paid for by the cheap ones.
Theorem— Doubling gives constant amortised appends
If a dynamic array starts with capacity 1 and doubles its capacity whenever an append finds it full, then any sequence of appends performs fewer than copies in total, so each append costs amortised.
Proof
Copies happen only when the array is full, that is, when its size is a power of two: at sizes where . The total number of items copied is
Adding the writes of the new items themselves, the whole sequence costs fewer than steps, which is per append.
∎
The same argument works for any growth factor : the copy sizes form a geometric series summing to at most about . CPython uses a gentle factor of about plus a small constant (see listobject.c in the references), trading more copies for less wasted memory. Growing by a fixed amount instead, say 100 slots at a time, breaks the guarantee: copy sizes add up to .
import sys
# Watch a real list's memory jump only now and then as it grows
xs = []
last = sys.getsizeof(xs)
changes = []
for i in range(1, 129):
xs.append(i)
size = sys.getsizeof(xs)
if size != last:
changes.append(i)
last = size
print("The list's block grew when its length reached:", changes)
# Count copies for two growth strategies
def copies_needed(n, grow):
capacity, size, copies = 1, 0, 0
for _ in range(n):
if size == capacity:
copies += size # move every item to the new block
capacity = grow(capacity)
size += 1
return copies
def double(c):
return 2 * c
def add_100(c):
return c + 100
for n in [1000, 10_000, 100_000]:
d = copies_needed(n, double)
a = copies_needed(n, add_100)
print(f"n = {n:>7}: doubling {d:>7} copies ({d / n:.2f} per append);"
f" +100: {a:>10} copies ({a / n:.1f} per append)")The exact sizes depend on the Python version and on whether it runs on a 64-bit machine or (as in the browser) a 32-bit WebAssembly build, but the gaps between growth points widen as the list gets longer. And the copy counts tell the story: with doubling, the cost per append stays below 2 however large gets; with fixed-size growth, it climbs with . You'll build a dynamic array yourself in Lists, stacks and queues.
Timing experiments
Analysis predicts; experiment checks. The most useful experiment is the doubling experiment: run the program on inputs of size , , , … and look at the ratio of successive times. If , then
so a ratio near 2 suggests linear growth, near 4 quadratic, near 8 cubic. The unknown constant , which depends on the machine, cancels out. Taking of the ratio estimates the exponent directly.
Some care makes timings trustworthy: use time.perf_counter() (a high-resolution clock), repeat each measurement and keep the minimum (other activity on the machine can only make a run slower, never faster), and use inputs large enough that each run takes at least a few milliseconds. Python's timeit module packages these habits.
import math
import time
def has_duplicate_pairs(ids):
n = len(ids)
for i in range(n):
for j in range(i + 1, n):
if ids[i] == ids[j]:
return True
return False
def has_duplicate_set(ids):
seen = set()
for x in ids:
if x in seen:
return True
seen.add(x)
return False
def best_time(f, data, repeats=3):
best = float("inf")
for _ in range(repeats):
start = time.perf_counter()
f(data)
best = min(best, time.perf_counter() - start)
return best
def doubling(f, sizes):
previous = None
for n in sizes:
t = best_time(f, list(range(n))) # distinct items: the worst case
if previous is None:
print(f" n = {n:>7}: {t * 1000:8.2f} ms")
else:
ratio = t / previous
print(f" n = {n:>7}: {t * 1000:8.2f} ms ratio {ratio:4.1f} exponent about {math.log2(ratio):.1f}")
previous = t
print("all pairs:")
doubling(has_duplicate_pairs, [400, 800, 1600])
print("with a set:")
doubling(has_duplicate_set, [50_000, 100_000, 200_000])Your times will differ from anyone else's, but the ratios should come out near 4 for the pairs version and near 2 for the set version, as the analysis predicts. If a measured ratio disagrees with your analysis, one of them is wrong, and finding out which is always instructive. (For tiny , fixed overheads dominate and ratios drift towards 1.)
Memory can be analysed the same way. has_duplicate_set uses extra memory for its set, while has_duplicate_pairs uses . Spending memory to save time is one of the most common trades in computing.
Common misconceptions
Misconception
" means it takes steps." It means at most a constant times , for large enough . An algorithm taking steps is , and so is one taking steps: is only an upper bound.
Misconception
"Big-O means worst case; big-Ω means best case." The case and the notation are independent choices. You can give an bound on the best case or an bound on the worst case. "Comparison sorting needs comparisons in the worst case" is a famous lower bound on a worst case, which you'll meet in Searching and sorting.
Misconception
"Constants never matter." They don't affect the growth class, but they matter enormously in practice. For small inputs a algorithm with a tiny constant can beat a one with a large constant, which is why Python's own sort switches to insertion sort for short stretches of data. Memory access patterns can also change real speed by large factors, as The memory hierarchy explains.
Misconception
"Computers are so fast now that efficiency doesn't matter." Unless the algorithm is linear or better, a faster machine multiplies the solvable problem size by much less than its speed-up, and data keeps growing too.
Where the notation came from
The symbol was introduced by the number theorist Paul Bachmann in 1894 and popularised by Edmund Landau, which is why these are still called Landau symbols; they described the error in approximations, such as counting primes. In 1965 Juris Hartmanis and Richard Stearns measured problems by the time a machine needs as a function of input length, founding complexity theory (Turing Award, 1993), and in the same year Alan Cobham and Jack Edmonds independently proposed "polynomial time" as the mathematical stand-in for "efficient". In 1976 Donald Knuth, whose The Art of Computer Programming helped make the analysis of algorithms a discipline, wrote a short letter fixing the meanings of and used here; before that, authors used in different senses.
Exercises
1. Measuring the cost of a program
CoreHumanWhich of these statements are true? Choose all that apply.
2. Measuring the cost of a program
Warm-upHumanTo prove , you choose the constant . What is the smallest such that for every ?
3. Measuring the cost of a program
CoreComputationalWhat is the running time of this code, as a function of ?
total = 0
for i in range(n):
j = n
while j > 1:
j = j // 2
total += 1
for k in range(n):
total += k
4. Measuring the cost of a program
CoreHumanAn algorithm with running time processes items in one hour. You move it to a computer that is 100 times faster. Roughly how many items can it process in one hour now?
5. Measuring the cost of a program
CoreHumanLinear search checks the items of a list from the front until it finds the target. Which statement is correct and most informative?
6. Measuring the cost of a program
CoreComputationalThe starter is the all-pairs duplicate checker from the lesson. It is correct, but it makes comparisons. Rewrite has_duplicate(items) so that it does work on average, using a set.
The checker counts how many times items are compared with ==: on a list of 1000 distinct items, your function may make at most 2000 comparisons.
7. Measuring the cost of a program
CoreComputationalWrite estimate_exponent(n1, t1, n2, t2), which takes two measurements (input size n1 took t1 seconds, size n2 took t2 seconds) and returns the exponent for which fits both. For example, if doubling multiplies the time by 4, the answer is 2.
Hint: from , solve for with logarithms. import math gives you math.log.
8. Measuring the cost of a program
StretchComputationalSimulate a dynamic array. Write total_copies(n, factor) that returns how many item copies are made while appending n items to an array that:
- starts with
capacity = 1andsize = 0; - on each append, if
size == capacity, first copies allsizeitems to a new block and setscapacity = max(capacity + 1, int(capacity * factor)); - then stores the new item (
size += 1; this write is not a copy).
For factor = 2 the answer for n = 5 is 1 + 2 + 4 = 7. Then check the theorem: the tests confirm that for factor = 2 the copies are always fewer than 2 * n.
Further reading and resources
- Big Omicron and big Omega and big Theta · Donald E. Knuth · 1976The short letter in SIGACT News that fixed the meanings of O, Ω and Θ used in computer science today.
- On the computational complexity of algorithms · J. Hartmanis and R. E. Stearns · 1965The paper that founded computational complexity theory as a field.
- MIT 6.006 Introduction to Algorithms (Spring 2020) · MIT OpenCourseWareFree lectures and notes covering asymptotic analysis and the data structures of this level.
- timeit: measure execution time of small code snippets · Python Software Foundation
- CPython source: Objects/listobject.cThe over-allocation rule for lists is in the resize function, with a comment giving the growth pattern.