You have a function that answers instantly with a hundred elements and makes you wait half an hour with a million, while its twin, written in an apparently identical way, handles both sizes. The stopwatch tells you that one is slower, not why, and above all it does not tell you what will happen with ten million elements. Big-O notation exists for this: it is a statement about how the number of operations grows as the input grows, and you can check it by counting operations instead of watching the clock. In this article you use it, take it apart and verify it on real programs.
This is the first article in the Algorithms and Data Structures series, so you need no prerequisites beyond being able to read a loop. All listings are in Python 3.14 with the standard library only and run with python3 -I; the outputs shown are the ones obtained by running them, twice with an identical result. The complexities are not asserted: they are counted, and where a result is a formula I made a second, independent calculation of it.
What O, Ω and Θ really claim
Saying that f(n) = O(g(n)) means that there exist two constants, c > 0 and n₀, such that f(n) ≤ c·g(n) for every n ≥ n₀. The two constants are the "witnesses" of the claim: without them the sentence says nothing, and with them it can be refuted by a single counterexample. Take f(n) = 3n² + 10n + 7, a plausible cost for a function with a double loop, a single loop and a few fixed instructions. The listing proposes c = 4 and n₀ = 11 and tests them in three ways.
# Big-O as a checkable claim: is f(n) = 3n^2 + 10n + 7 in O(n^2)?
def f(n):
return 3 * n * n + 10 * n + 7
c, n0 = 4, 11 # the two "witnesses" of the definition: f(n) <= c * n^2 for every n >= n0
# 1) numeric check over a wide range (not a proof)
assert all(f(n) <= c * n * n for n in range(n0, 20001))
print("f(n) <= 4n^2 for every n from", n0, "to 20000: true")
# 2) the witness n0 is not arbitrary: one step earlier the inequality fails
print("n = 10:", f(10), "<=", c * 10 * 10, "->", f(10) <= c * 100)
# 3) independent check, algebraically: f(n) <= 4n^2 <=> n^2 - 10n - 7 >= 0
g = lambda n: n * n - 10 * n - 7
first_ok = next(n for n in range(1, 100) if g(n) >= 0)
print("first n with n^2 - 10n - 7 >= 0:", first_ok)
# 4) the lower bound: f(n) >= 3n^2 for every n >= 1, so f is also Omega(n^2) => Theta(n^2)
assert all(f(n) >= 3 * n * n for n in range(1, 20001))
print("f(n) >= 3n^2 for every n from 1 to 20000: true")
# Output:
# f(n) <= 4n^2 for every n from 11 to 20000: true
# n = 10: 407 <= 400 -> False
# first n with n^2 - 10n - 7 >= 0: 11
# f(n) >= 3n^2 for every n from 1 to 20000: trueThe first check walks the range from 11 to 20,000 and is not a proof: it is the trap that springs if the witnesses are wrong. The second shows that n₀ is not decorative, because at n = 10 the inequality fails (407 against 400). The third is the independent calculation: f(n) ≤ 4n² is equivalent to n² − 10n − 7 ≥ 0, and the first integer that satisfies it is exactly 11. Finally, the lower bound f(n) ≥ 3n² holds from n = 1, and the two bounds together give Θ(n²).
The three notations read as three different questions about the same function.
- O (upper bound): the cost does not grow faster than g, up to a constant.
- Ω (lower bound): the cost does not grow more slowly than g, up to a constant.
- Θ (tight bound): both hold, so g describes the growth with no slack.
The distinction matters more than it seems, because "it is O(n²)" is also true of an algorithm that costs n: it is a bound, not a description. When someone in an interview or a code review says "it is O(n²)", the useful question is whether they mean Θ or just a loose bound. For reference texts on the formal definition and its consequences, the classic textbook is Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, fourth edition, MIT Press 2022 (cited, not read for this article: the publisher's page answered 403 to my client).
Best, worst and average: three different numbers for the same code
The same function has a different cost depending on the input, which is why we talk about best, worst and average case. In linear search the best case is finding the element in the first position, the worst is never finding it, and the average depends on an assumption: here every position is equally likely. The listing counts comparisons, not seconds, and for the average case it takes the exact mean over all possible positions instead of sampling.
# Three scenarios of linear search, measured by COUNTING comparisons (not seconds)
def linear_search(arr, target):
comparisons = 0
for i, x in enumerate(arr):
comparisons += 1
if x == target:
return i, comparisons
return -1, comparisons
print(f"{'n':>6} {'best':>9} {'worst (absent)':>19} {'average (present)':>17} {'(n+1)/2':>9}")
for n in (10, 100, 1000, 10000):
arr = list(range(n))
best = linear_search(arr, arr[0])[1]
worst = linear_search(arr, -1)[1]
# exact mean over ALL possible positions, each with the same probability
mean = sum(linear_search(arr, t)[1] for t in arr) / n
print(f"{n:>6} {best:>9} {worst:>19} {mean:>17.1f} {(n + 1) / 2:>9.1f}")
# Output:
# n best worst (absent) average (present) (n+1)/2
# 10 1 10 5.5 5.5
# 100 1 100 50.5 50.5
# 1000 1 1000 500.5 500.5
# 10000 1 10000 5000.5 5000.5The average-case column matches (n + 1)/2 down to the decimal: the mean of the numbers from 1 to n is exactly that. The worst case costs n comparisons and the best one, so the interval is huge and choosing which number to quote is not a detail. For a service with a latency target on the 99th percentile the worst case matters; for a batch job that runs over the whole archive the average matters. If you do not know which of the two concerns you, you have discovered that you are missing information about the load, not about the algorithm.
Growth classes as counts
The classes you will meet everywhere are few, and you recognize them from the shape of the loops.
- O(1): a fixed number of steps, like reading
a[k]in a list. - O(log n): at every step the input is halved, as in binary search.
- O(n): one pass over all the elements.
- O(n log n): one pass for each level of halving, as in efficient sorts.
- O(n²): two nested loops over the same input.
The list is ordered by growth, and the order is the substance: each class, for large enough n, overtakes all the previous ones. To see it with numbers, the listing implements one example per class with a counter and runs them on n = 64, 128, … 4096. Then it computes the slope on the log-log plane: if doubling n multiplies the operations by 2p, the slope is p.
# Growth classes as COUNTS of elementary operations, on n = 2^k
import math
def count_linear(n): # one loop: n steps
ops = 0
for _ in range(n):
ops += 1
return ops
def count_quadratic(n): # two nested loops: n^2 steps
ops = 0
for _ in range(n):
for _ in range(n):
ops += 1
return ops
def count_log(n): # halving: floor(log2 n) + 1 steps
ops = 0
while n >= 1:
n //= 2
ops += 1
return ops
def count_nlogn(n): # outer loop n, inner loop with halving
return sum(count_log(n) for _ in range(n))
sizes = [2 ** k for k in range(6, 13)] # 64 ... 4096
funcs = [("log", count_log), ("linear", count_linear),
("n log n", count_nlogn), ("quadratic", count_quadratic)]
rows = {name: [fn(n) for n in sizes] for name, fn in funcs}
print("n ", *[f"{name:>11}" for name, _ in funcs])
for i, n in enumerate(sizes):
print(f"{n:<7}", *[f"{rows[name][i]:>11}" for name, _ in funcs])
# log-log slope between the last pair of sizes: doubling n multiplies the operations by 2^slope
print("\nlog-log slope between n=2048 and n=4096")
for name, _ in funcs:
slope = math.log2(rows[name][-1] / rows[name][-2])
print(f" {name:<11} {slope:.3f}")
# Output:
# n log linear n log n quadratic
# 64 7 64 448 4096
# 128 8 128 1024 16384
# 256 9 256 2304 65536
# 512 10 512 5120 262144
# 1024 11 1024 11264 1048576
# 2048 12 2048 24576 4194304
# 4096 13 4096 53248 16777216
#
# log-log slope between n=2048 and n=4096
# log 0.115
# linear 1.000
# n log n 1.115
# quadratic 2.000Read the table by columns: the logarithm goes from 7 to 13 while n is multiplied by 64, and the linear and quadratic columns follow the expected shape. The slope says the same thing in a single number: 1.000 for linear, 2.000 for quadratic, 0.115 for the logarithm and 1.115 for n log n. This last value is the reason why a log-log plot of an n log n algorithm looks "almost linear but a little crooked": the slope is 1 + 1/log₂ n, and it tends to 1 slowly.
An often-quoted piece of arithmetic, which here is only arithmetic: if a machine executed 10⁹ simple operations per second (an assumption, not a measurement), an algorithm of n² = 10¹² operations with n = 10⁶ would take 1,000 seconds, about 16 minutes, while one of about 2·10⁷ would take 0.02. The difference is not "fast against slow" but "possible against impossible", and it depends only on the count.
When "O(2ⁿ)" is a wrong shortcut
Many texts say that naive recursive Fibonacci is O(2ⁿ). As an upper bound it is true, but as a description it is wrong, and the count shows it. The listing counts the calls to fib and the maximum recursion depth, and compares the result with an iterative version (an independent reference, O(n) in time and O(1) in space) and with the closed form 2·F(n+1) − 1, which is the exact number of calls.
# O(2^n) or not? Recursive Fibonacci: count the calls and the maximum depth
import math
calls = 0
depth = 0
max_depth = 0
def fib(n):
global calls, depth, max_depth
calls += 1
depth += 1
max_depth = max(max_depth, depth)
result = n if n < 2 else fib(n - 1) + fib(n - 2)
depth -= 1
return result
def fib_iter(n): # independent reference, O(n) time and O(1) space
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
prev = None
print(f"{'n':>3} {'calls':>10} {'2F(n+1)-1':>10} {'ratio':>9} {'max depth':>9}")
for n in range(10, 31, 4):
calls = depth = max_depth = 0
assert fib(n) == fib_iter(n)
formula = 2 * fib_iter(n + 1) - 1 # closed form of the number of calls
assert calls == formula
ratio = f"{calls / prev:.3f}" if prev else "-"
print(f"{n:>3} {calls:>10} {formula:>10} {ratio:>9} {max_depth:>9}")
prev = calls
phi = (1 + math.sqrt(5)) / 2
print("\nexpected ratio between n and n+4: phi^4 =", round(phi ** 4, 3), "(not 2^4 = 16)")
# Output:
# n calls 2F(n+1)-1 ratio max depth
# 10 177 177 - 10
# 14 1219 1219 6.887 14
# 18 8361 8361 6.859 18
# 22 57313 57313 6.855 22
# 26 392835 392835 6.854 26
# 30 2692537 2692537 6.854 30
#
# expected ratio between n and n+4: phi^4 = 6.854 (not 2^4 = 16)The calls match the formula in every row (the assert did not fire), and the ratio between n and n + 4 converges to 6.854 and not to 16: the growth is Θ(φⁿ) with φ ≈ 1.618, the golden ratio, not 2ⁿ. The depth column says something else: the space used by the stack is linear, n levels, because the recursion always descends the n − 1 branch first. So the same program has exponential time and linear space, and the two analyses must be done separately.
Extra space, excluding the input, is the second resource to count: an "in-place" function uses a constant or logarithmic amount of it, one that copies its input uses a proportional amount. In the next article, Sorting algorithms: bubble, merge, quick, heap, you will see that merge sort and quicksort have the same average time but very different space.
Amortized analysis: the append that sometimes costs n
Some operations almost always cost little and now and then cost a great deal. The append of a dynamic list writes into a free cell, but when the reserved memory is full it must allocate a larger block and copy everything. The amortized cost is the total cost of a sequence of operations divided by their number, and it depends on the growth strategy. The listing compares two strategies over N appends: doubling the capacity and increasing it by 16 slots each time.
# Dynamic array: how many copies does a sequence of N appends cost?
def appends(N, grow):
"""grow(cap) -> new capacity. Returns total copies and the cost of the worst single append."""
cap, size, copies, worst = 1, 0, 0, 0
for _ in range(N):
cost = 1 # writing the element
if size == cap: # full: allocate and copy everything
cost += size
copies += size
cap = grow(cap)
size += 1
worst = max(worst, cost)
return copies, worst
print(f"{'N':>8} | {'doubling: copies':>16} {'copies/N':>8} {'worst':>9} | {'+16: copies':>11} {'copies/N':>8}")
for N in (1000, 10000, 100000):
c2, w2 = appends(N, lambda c: 2 * c)
c16, _ = appends(N, lambda c: c + 16)
print(f"{N:>8} | {c2:>16} {c2 / N:>8.3f} {w2:>9} | {c16:>11} {c16 / N:>8.1f}")
# Banker's method: each append takes in 'charge' units and pays the real cost.
def min_bank(N, charge):
cap, size, bank, lowest = 1, 0, 0, 0
for _ in range(N):
cost = 1
if size == cap:
cost += size
cap *= 2
size += 1
bank += charge - cost
lowest = min(lowest, bank)
return lowest
print("\nminimum balance with a charge of 2 per append:", min_bank(100000, 2))
print("minimum balance with a charge of 3 per append:", min_bank(100000, 3))
# Output:
# N | doubling: copies copies/N worst | +16: copies copies/N
# 1000 | 1023 1.023 513 | 31311 31.3
# 10000 | 16383 1.638 8193 | 3120625 312.1
# 100000 | 131071 1.311 65537 | 312456250 3124.6
#
# minimum balance with a charge of 2 per append: -65534
# minimum balance with a charge of 3 per append: 0With doubling, the total copies stay below 2N (1,023, 16,383 and 131,071 for N = 1,000, 10,000 and 100,000): they are always a power of two minus one, so the copies/N ratio oscillates between 1 and 2 and does not grow. With the fixed increment the copies per append rise with N (31, 312, 3,124), because the sum of an arithmetic progression is quadratic. The "worst" on the right stays huge (65,537 for N = 100,000) and this is the point to remember: amortized does not mean that every operation is fast.
The second part of the listing is Tarjan's banker's method (Amortized Computational Complexity, SIAM Journal on Algebraic Discrete Methods, 1985, DOI 10.1137/0606031, whose metadata I verified but whose text I did not read). Each append takes in a fixed unit and pays the real cost; if the balance never drops below zero, that fixed charge is an upper bound on the amortized cost. With 3 units the minimum balance is 0 and the account holds; with 2 units the balance reaches −65,534 and the argument collapses. The three is not magic: one unit pays for the write, two accumulate to copy the element itself and one companion at the next doubling.
And the real list? Python's documentation gives append as amortized O(1), with the note that a single operation can cost O(n) when the space is resized. The second listing observes it from the outside, reading sys.getsizeof after every append.
# How a CPython list really grows: count the changes in the reserved capacity
import sys
lst = []
last, reallocs = sys.getsizeof(lst), 0
for i in range(1_000_000):
lst.append(i)
now = sys.getsizeof(lst)
if now != last:
reallocs += 1
last = now
print("Python", sys.version.split()[0])
print("appends performed: 1000000, capacity changes observed:", reallocs)
print("bytes reserved at the end:", sys.getsizeof(lst), "for", len(lst), "elements")
print("reserved/used ratio:", round(sys.getsizeof(lst) / (8 * len(lst)), 3))
# Output:
# Python 3.14.4
# appends performed: 1000000, capacity changes observed: 86
# bytes reserved at the end: 8448728 for 1000000 elements
# reserved/used ratio: 1.056The result depends on the version, which is why it is printed: with Python 3.14.4 the reserved capacity changed 86 times in a million appends, and at the end the list reserves about 5.6% more memory than needed. Few changes, at growing distances, are the signature of proportional growth rather than constant growth. Do not derive a growth factor from this as a general rule: it is an implementation detail that may change.
Building the worst case instead of hoping for it
Declaring a worst case without showing it is a dangerous habit: insertion sort is O(n²), but what is the constant, and when do you reach that limit? The listing implements it counting comparisons and moves, verifies it on 2,000 random inputs with a fixed seed against sorted and against an independent reference (the number of inversions, that is the out-of-order pairs, computed by brute force), and then builds the three cases.
# Best, worst and average case built on purpose, with the count of comparisons and moves
import random
def insertion_sort(a):
a = a[:]
comparisons = moves = 0
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0:
comparisons += 1
if a[j] > key:
a[j + 1] = a[j]
moves += 1
j -= 1
else:
break
a[j + 1] = key
return a, comparisons, moves
def inversions(a): # independent reference: out-of-order pairs, by brute force
return sum(1 for i in range(len(a)) for j in range(i + 1, len(a)) if a[i] > a[j])
rng = random.Random(2026) # fixed seed: same output on every run
for _ in range(2000): # correctness and moves == inversions, on 2000 inputs
a = [rng.randrange(50) for _ in range(rng.randrange(0, 30))]
out, _, moves = insertion_sort(a)
assert out == sorted(a) and moves == inversions(a)
print(f"{'n':>5} {'sorted':>9} {'reversed':>9} {'n(n-1)/2':>9} {'random (mean of 200)':>20} {'n^2/4':>9}")
for n in (50, 100, 200, 400):
best = insertion_sort(list(range(n)))[1]
worst = insertion_sort(list(range(n, 0, -1)))[1]
avg = sum(insertion_sort(rng.sample(range(n), n))[1] for _ in range(200)) / 200
print(f"{n:>5} {best:>9} {worst:>9} {n * (n - 1) // 2:>9} {avg:>20.0f} {n * n / 4:>9.0f}")
# Output:
# n sorted reversed n(n-1)/2 random (mean of 200) n^2/4
# 50 49 1225 1225 653 625
# 100 99 4950 4950 2569 2500
# 200 199 19900 19900 10080 10000
# 400 399 79800 79800 40331 40000On the already sorted input the comparisons are n − 1, and on the reversed input they are exactly n(n − 1)/2: the table matches the formula in every row. The random case, averaged over 200 runs with a fixed seed, is close to n²/4 and the difference (653 against 625 for n = 50) is the linear term that the exact formula contains and its simplified form ignores. The fact that the moves are equal to the inversions, verified 2,000 times, explains why a nearly sorted input is almost free: the cost measures how disordered the input is, not only how long it is.
Hidden constants and why the notation is not enough
Big-O throws away the constants, and in production the constants decide. Two O(n log n) algorithms can have very different costs because of the way they access memory, and an O(n²) one can beat an O(n log n) one on small inputs. I did not measure it here, because the counts in this article are deliberately machine-independent, and therefore say nothing about times: a figure like "10 times faster thanks to the cache" without a reproducible measurement is exactly the kind of sentence this series avoids.
A documented confirmation does exist in the source, though: the implementation notes of CPython's sort (listsort.txt) say that a sorted run shorter than a minimum length (minrun) is extended to that length with a stable binary insertion, in which the position is found with a binary search, before being merged with the others. If insertion, quadratic in the general case, ends up inside Python's default sort, it is because asymptotic notation describes behavior for large n and practice often works with small n.
How to use counts in your work
The method these listings show you applies to any function. First you form a hypothesis about the complexity by reading the loops, then you instrument the code with a counter on the operations you care about (comparisons, accesses, copies), then you run it on doubling sizes and compute the log-log slope between consecutive pairs. If the slope does not match the hypothesis, you have found an error in the analysis or in the code: it is the most useful moment of the process, because no stopwatch would have told you with this sharpness.
Counting goes alongside timing, it does not replace it. Times tell you whether the constant is acceptable, and must be reported as intervals, declaring machine, version and number of runs. Counting tells you how your code will scale, and has the advantage of being identical on any computer, repeatable and comparable in a code review.
When asymptotic notation is not enough
- Small inputs: below a few dozen elements the constant dominates and the asymptotic class may point to the wrong algorithm.
- Non-uniform operations: counting "comparisons" or "accesses" as equal units hides the fact that a write to disk costs orders of magnitude more than an addition.
- Rare worst case: an amortized O(1) operation can still violate a latency target if its peak falls at the wrong moment.
- Input distribution: the average holds only under the assumption with which it was computed, and real data rarely respect it.
None of these limits makes the notation useless; they make it a first filter. If two solutions have different classes and the input will grow, the class decides; if they have the same class or the input will stay small, the decision passes to measurement and to the readability of the code.
Exercises
- In the first listing use f(n) = 5n² + 2n and find by hand two witnesses c and n₀, then verify with a loop.
- Write binary search on a sorted list, counting the comparisons, and verify that they do not exceed ⌊log₂ n⌋ + 1.
- In the dynamic array listing try a growth factor of 1.5 instead of 2 and observe the copies/N ratio.
- Build the worst input for linear search with duplicates and explain why the worst case stays n.
The exercises are in order of difficulty, but can be done in any order: the second prepares the article on search, the third shows that the "2" of doubling is a choice and not a law. If a result does not add up, rerun the listing with one more counter instead of rereading the theory.
Frequently asked questions
What is the difference between O(n) and Θ(n)?
O(n) is only an upper bound: a function that always costs 5 steps is also O(n). Θ(n) says that the growth is linear both upward and downward, so it describes the cost precisely, up to constants.
Why is timing the code not enough?
Time depends on the machine, the load and the interpreter version, and concerns only the sizes you tried. The operation count is identical everywhere and shows how the cost grows even beyond the sizes measured.
Is a Python list's append really O(1)?
It is amortized O(1) according to Python's documentation: a sequence of N appends costs O(N) in total, but a single operation can cost O(n) when the reserved memory is enlarged.
What you can do now
You can state Big-O with its witnesses and refute it with a counterexample, tell the best, average and worst case apart and build them instead of hoping for them, and read a log-log slope as a diagnosis. You know that "O(2ⁿ)" and "amortized O(1)" are precise statements that can be counted, and you have a method, hypothesis, counter, slope, to verify your own. The next step, the article on sorting, applies the same method to four concrete algorithms; linear, binary and hash-table search and the linear structures close this first block of the series.
The same series also includes binary search trees and AVL trees and the closing article on dynamic programming.
Sources
- Python Documentation - Time complexity of built-in types: took the complexity of
list.appendas amortized O(1) and the note on resizing; consulted on 2026-11-13. - CPython, Objects/listsort.txt: took the description of the binary insertion used for short runs; text read, consulted on 2026-11-13.
- R. E. Tarjan, Amortized Computational Complexity, SIAM J. Algebraic Discrete Methods 6(2), 1985: cited for the banker's method; title, author and journal verified via Crossref on 2026-11-13, text not read.
- Measurements: the commands are the seven listings of the article, run with Python 3.14.4 (
python3 -I) on 2026-11-13.
Commenti
Caricamento commenti...
Sign in to comment