When you say "this algorithm is O(n log n)", are you saying something precise, or repeating a formula you memorised? In this first article of the series we take the three notations we will use throughout, Big-O, Omega and Theta, read them from their definition and put them to the test with programs that count operations instead of timing them.
Why we count operations, not seconds
Two algorithms that sort a thousand numbers can finish at the same instant and behave in opposite ways on ten million. A stopwatch will not show it, for two reasons: the time depends on the machine, the language and whatever else happens to be running, and it measures only one size at a time. Jeff Erickson, in his open-access textbook, starts from here with a deliberately silly example, the time needed to sing a nursery rhyme of n verses: whoever sings faster or slower changes the constant, but doubling n still doubles the time, and this is the "asymptotic" growth Θ(n). His practical advice is to count how many times the algorithm executes a given instruction.
Asymptotic notation exists to say how the cost of an algorithm grows as the size of the input grows, not how fast it is on a hundred elements. That is why in this whole article the programs count comparisons, which are the same on any computer, and report the ratio between the count and the declared growth. The only times in the article are the hypothetical ones in the final table, declared as such.
The definitions, read at the source
I take the definitions from the chapter on asymptotic notation in Mathematics for Computer Science (Lehman, Leighton, Meyer, MIT, open text, § 14.7), because they are written precisely and without the vague wording of lecture notes. All of them speak about functions f and g from the naturals (or the reals) to themselves, not about algorithms: the algorithm enters only when you decide which cost function to call f.
- O (upper bound).
f = O(g)if there exist a constantc > 0and ann₀such that for everyn ≥ n₀we have|f(n)| ≤ c · g(n). The function f does not grow faster than g, up to a constant. - Ω (lower bound).
f = Ω(g)ifg = O(f): f grows at least as much as g, up to a constant. - Θ (tight bound).
f = Θ(g)if both hold,f = O(g)andg = O(f): f and g are equal up to a constant factor. - Little o (strictly slower).
f = o(g)if the limit off(n)/g(n)as n tends to infinity is 0. Then f grows significantly more slowly than g, which is a stronger statement than O.
The first three are size relations between functions, with a tolerance constant; the fourth removes the tolerance and asks the ratio to vanish. If you swap the roles of O and Ω the meaning flips, and it is the most common mistake: "at least O(n²)" is meaningless, because O only provides upper bounds; for a lower bound you write Ω(n²). The same text warns that O(g) is not a number and that the "=" sign is a historical convention: from 2n = O(n) it does not follow that O(n) = 2n.
The listing below tests the definitions on small cases. The function primo_controesempio (Italian for "first counterexample") looks, between n₀ and a maximum, for the first n where the inequality of the definition fails. It is a finite check and proves nothing: the proof of 3n² + 2n + 7 ≤ 4n² for n ≥ 4 is algebra (it is equivalent to n² − 2n − 7 ≥ 0, true from n ≥ 1 + √8 ≈ 3.83). The program is there to catch the mistakes of whoever picks c and n₀ by eye.
# Look for a counterexample to the inequality in the definition of O, over a finite range.
# Careful: a finite check proves NOTHING, it can only find mistakes.
def primo_controesempio(f, g, c, n0, n_max):
for n in range(n0, n_max + 1):
if f(n) > c * g(n):
return n
return None
f = lambda n: 3 * n**2 + 2 * n + 7
print("f(n)=3n^2+2n+7 against g(n)=n^2")
print(" c=4, n0=4 :", primo_controesempio(f, lambda n: n**2, 4, 4, 10**6))
print(" c=4, n0=3 :", primo_controesempio(f, lambda n: n**2, 4, 3, 10**6))
print(" c=3, n0=1 :", primo_controesempio(f, lambda n: n**2, 3, 1, 10**6))
print("100n against n^2 (c=1)")
print(" n0=1 :", primo_controesempio(lambda n: 100 * n, lambda n: n**2, 1, 1, 1000))
print(" n0=100:", primo_controesempio(lambda n: 100 * n, lambda n: n**2, 1, 100, 1000))
print("4^n against 2^n: ratio f/g")
for n in (10, 20, 30):
print(f" n={n}: {4**n // 2**n}")
print("1000*n^1.9 divided by n^2 (limit 0, but very slowly)")
for esp in (3, 6, 12, 30):
n = 10**esp
print(f" n=10^{esp}: {1000 * n**-0.1:.2f}")
# Output (two runs, identical output):
# f(n)=3n^2+2n+7 against g(n)=n^2
# c=4, n0=4 : None
# c=4, n0=3 : 3
# c=3, n0=1 : 1
# 100n against n^2 (c=1)
# n0=1 : 1
# n0=100: None
# 4^n against 2^n: ratio f/g
# n=10: 1024
# n=20: 1048576
# n=30: 1073741824
# 1000*n^1.9 divided by n^2 (limit 0, but very slowly)
# n=10^3: 501.19
# n=10^6: 251.19
# n=10^12: 63.10
# n=10^30: 1.00
The first three lines of output show that the two witnesses really are a pair: with c = 4 and n₀ = 4 there is no counterexample, but lowering n₀ to 3 the inequality breaks exactly at n = 3, where 3·9 + 6 + 7 = 40 exceeds 4·9 = 36, and with c = 3 it breaks immediately. Likewise 100n is below n² only from n = 100: under that threshold the term with the large constant wins. The ratio 4ⁿ / 2ⁿ is 2ⁿ and does not stay bounded, so 4ⁿ is not O(2ⁿ), even though 4 is "only a constant" larger than 2: it is the "exponential trap" that the text by Lehman and colleagues describes. Finally 1000·n^1.9 is o(n²), the ratio tends to zero, but the listing shows that at n = 10¹² it is still 63 and reaches 1 only at n = 10³⁰: "from some point on" can mean a very distant point.
A bound is not a case: the most widespread confusion
In lecture notes you often read "Big-O is the worst case, Omega is the best case". It is wrong, and the reason lies in the definitions just seen: O, Ω and Θ are relations between two functions, not names of cases. The "case" is another choice, made upstream: given an algorithm and a size n, there are many possible inputs and the cost changes from one to the next, so you must decide which function of n you are describing. There are three common choices: the cost on the worst input of size n, T_peggiore(n); the cost on the best one, T_migliore(n); the average over a declared distribution of inputs, T_medio(n) (the identifiers keep their Italian names: worst, best, average). Only after that do you choose a bound for that function, and each of the three can receive an O, an Ω and a Θ.
Linear search is the simplest case. The program counts how many times it compares the sought value with an element: if the value is in first position the comparisons are 1, if it is in last position they are n. I used a small class that increments a counter in __eq__, so the number is exact and does not depend on the computer. In the same test I look at what happens with the in operator on a list and on a set: the temptation to say that "Python lists are O(1)" comes from access by index, which is a different operation.
# We count equality comparisons, not seconds.
class Chiave:
confronti = 0
def __init__(self, v):
self.v = v
def __hash__(self):
return hash(self.v)
def __eq__(self, altro):
Chiave.confronti += 1
return self.v == altro.v
def conta(contenitore, valore):
Chiave.confronti = 0
valore in contenitore
return Chiave.confronti
print(f"{'n':>9} {'list (last)':>15} {'list (first)':>14} {'set':>4} comparisons/n")
for n in (1_000, 10_000, 100_000):
lista = [Chiave(i) for i in range(n)]
insieme = set(lista)
ultimo = conta(lista, Chiave(n - 1))
primo = conta(lista, Chiave(0))
set_ = conta(insieme, Chiave(n - 1))
print(f"{n:>9} {ultimo:>15} {primo:>14} {set_:>4} {ultimo / n:.3f}")
# Output (two runs, identical output):
# n list (last) list (first) set comparisons/n
# 1000 1000 1 1 1.000
# 10000 10000 1 1 1.000
# 100000 100000 1 1 1.000
The count on the list grows exactly like n, so the ratio with n stays 1.000 at every size: in the worst case, searching for a value in a list is Θ(n), and in the best case (first element) it costs 1 comparison, that is Θ(1). For the set the count is 1 at every size, because the value is found by computing the hash and comparing with a single candidate. The complexity table in the official Python documentation lists x in l as O(n) and x in s as O(1), with the caveat that the costs for dictionaries (and sets) are average-case times: if all the keys have the same hash, each operation costs O(n). A structure that "gives O(1)" gives it under an assumption about the data, and the assumption must be stated.
Insertion sort shows the same thing in sharper form, because the two cases are far apart. The listing counts comparisons on an already sorted input and on one in reverse order, and sets them next to the formula n(n−1)/2.
# One cost function, different inputs of the same size n.
def insertion_confronti(a):
a = list(a); c = 0
for i in range(1, len(a)):
k = a[i]; j = i - 1
while j >= 0:
c += 1
if a[j] > k:
a[j + 1] = a[j]; j -= 1
else:
break
a[j + 1] = k
return c
print(f"{'n':>6} {'sorted':>9} {'reversed':>10} {'n(n-1)/2':>10}")
for n in (100, 200, 400, 800):
ordinato = insertion_confronti(range(n))
inverso = insertion_confronti(range(n, 0, -1))
print(f"{n:>6} {ordinato:>9} {inverso:>10} {n * (n - 1) // 2:>10}")
# Output (two runs, identical output):
# n sorted reversed n(n-1)/2
# 100 99 4950 4950
# 200 199 19900 19900
# 400 399 79800 79800
# 800 799 319600 319600
On the sorted input the comparisons are n−1; on the reversed one they are exactly n(n−1)/2, as the last column shows. So T_migliore(n) = Θ(n) and T_peggiore(n) = Θ(n²). Said of "the time of the algorithm" without further specification, the only thing true for every input is that the cost lies between Ω(n) and O(n²): there is no single Θ, because the cost function is not unique. It follows that "Ω is the best case" is as false as "O is the worst case": for linear search T_migliore(n) is O(1), so an O describes the best case perfectly well, and T_peggiore(n) is Ω(n), so an Ω can also describe the worst case.
Quicksort and merge sort: three functions, two algorithms
Quicksort makes it plain why the function has to be declared. With the pivot chosen as the first element, the worst-case function and the average-case function have different orders. One can honestly say: T_peggiore(n) = Θ(n²) (already sorted input, extremely unbalanced partitions) and T_medio(n) = Θ(n log n) if the average is taken over all equiprobable permutations. So "quicksort is O(n²)" is true (it is the upper bound of the worst case, and therefore holds for every case), while "it is Θ(n log n)" makes no sense without saying which case.
The program counts the element-pivot comparisons of quicksort on sorted input and on random permutations, with twenty fixed seeds for each size and the mean reported. As an independent check, the column formula is the expected value in closed form 2(n+1)H_n − 4n, with H_n the harmonic number. For merge sort I counted the comparisons in the merge step on sorted input and on a random permutation.
import math, random
def quicksort_confronti(dati):
"""Pivot = first element. Counts element-pivot comparisons."""
c = 0
pila = [list(dati)]
while pila:
a = pila.pop()
if len(a) <= 1:
continue
p = a[0]
c += len(a) - 1
pila.append([x for x in a[1:] if x < p])
pila.append([x for x in a[1:] if x >= p])
return c
def merge_confronti(a):
if len(a) <= 1:
return list(a), 0
m = len(a) // 2
s, cs = merge_confronti(a[:m]); d, cd = merge_confronti(a[m:])
out, i, j, c = [], 0, 0, 0
while i < len(s) and j < len(d):
c += 1
if s[i] <= d[j]:
out.append(s[i]); i += 1
else:
out.append(d[j]); j += 1
out += s[i:] + d[j:]
return out, cs + cd + c
def attesi_quicksort(n): # closed form of the average case: 2(n+1)H_n - 4n
return 2 * (n + 1) * sum(1 / k for k in range(1, n + 1)) - 4 * n
print("quicksort, pivot = first element")
print(f"{'n':>6} {'sorted':>10} {'/n^2':>6} {'random':>9} {'formula':>9} {'/(n log2 n)':>12}")
for n in (500, 1000, 2000, 4000):
ordinato = quicksort_confronti(range(n))
prove = []
for seme in range(20):
r = random.Random(seme); d = list(range(n)); r.shuffle(d)
prove.append(quicksort_confronti(d))
media = sum(prove) / len(prove)
print(f"{n:>6} {ordinato:>10} {ordinato / n**2:>6.3f} {media:>9.0f} {attesi_quicksort(n):>9.0f} {media / (n * math.log2(n)):>12.3f}")
print("merge sort")
print(f"{'n':>6} {'sorted':>9} {'random':>9} {'n log2 n':>9} {'sor/(n log2 n)':>15} {'ran/(n log2 n)':>15}")
for n in (500, 1000, 2000, 4000):
_, o = merge_confronti(list(range(n)))
r = random.Random(1); d = list(range(n)); r.shuffle(d)
_, c = merge_confronti(d)
nl = n * math.log2(n)
print(f"{n:>6} {o:>9} {c:>9} {nl:>9.0f} {o / nl:>15.3f} {c / nl:>15.3f}")
# Output (two runs, identical output):
# quicksort, pivot = first element
# n sorted /n^2 random formula /(n log2 n)
# 500 124750 0.499 4810 4806 1.073
# 1000 499500 0.499 10957 10986 1.099
# 2000 1999000 0.500 24164 24730 1.102
# 4000 7998000 0.500 54646 54989 1.142
# merge sort
# n sorted random n log2 n sor/(n log2 n) ran/(n log2 n)
# 500 2216 3849 4483 0.494 0.859
# 1000 4932 8705 9966 0.495 0.873
# 2000 10864 19362 21932 0.495 0.883
# 4000 23728 42792 47863 0.496 0.894
On quicksort with sorted input, the ratio between comparisons and n² is 0.499-0.500: for n = 4000 the comparisons are 7,998,000, exactly n(n−1)/2. The mean on random input (4,810 for n = 500) follows the closed formula within 2.3% (the maximum gap, at n = 2000): same curve, so the sample of twenty seeds is reasonable. The ratio with n·log₂n rises slowly (1.073 → 1.142) because the asymptotic coefficient is 2 ln 2 ≈ 1.386 and there is a −n term that weighs less as n grows: for Θ(n log n) it is enough that the ratio stays within two constants, and it does. As for merge sort, the ratio with n·log₂n is 0.49-0.50 on the sorted input and 0.86-0.89 on the random one: in both cases it lies between two constants, so T(n) = Θ(n log n) in all cases. This is the real meaning of "has a well-defined Θ characterisation". I counted comparisons, not time: time also depends on allocations and moves, which are not measured here.
When in a popular article you read "quicksort is O(n log n)", that sentence implies the average case or a randomly chosen pivot, and it should be read that way: with the pivot on the first element the worst case stays quadratic, as the sorted-input column shows.
A lower bound on a problem: comparison sorting
Ω is the right language for saying that one cannot do better than a certain order, and it is said about the problem, not about an algorithm. The classic result is that every sorting algorithm that uses only comparisons performs, in the worst case, Ω(n log n) comparisons. The outline of the standard proof (I give it in full, I did not copy it from a source) is this: the possible inputs are the n! permutations, each comparison has two outcomes and therefore at most halves the number of permutations still compatible, and to tell them all apart you need at least ⌈log₂(n!)⌉ comparisons in the worst case. Since n! ≥ (n/2)^(n/2), we have log₂(n!) ≥ (n/2)·log₂(n/2), which is Ω(n log n).
The numerical test enumerates all the permutations for n from 2 to 8, counts the comparisons of merge sort on each and takes the maximum, to set beside the theoretical bound.
import itertools, math
def merge_confronti(a):
if len(a) <= 1:
return list(a), 0
m = len(a) // 2
s, cs = merge_confronti(a[:m]); d, cd = merge_confronti(a[m:])
out, i, j, c = [], 0, 0, 0
while i < len(s) and j < len(d):
c += 1
if s[i] <= d[j]:
out.append(s[i]); i += 1
else:
out.append(d[j]); j += 1
out += s[i:] + d[j:]
return out, cs + cd + c
print(f"{'n':>2} {'ceil(log2 n!)':>14} {'merge, worst case':>21}")
for n in range(2, 9):
peggiore = max(merge_confronti(list(p))[1] for p in itertools.permutations(range(n)))
print(f"{n:>2} {math.ceil(math.log2(math.factorial(n))):>14} {peggiore:>21}")
# Output (two runs, identical output):
# n ceil(log2 n!) merge, worst case
# 2 1 1
# 3 3 3
# 4 5 5
# 5 7 8
# 6 10 11
# 7 13 14
# 8 16 17
For n from 2 to 4 merge sort reaches the theoretical bound (1, 3, 5); for n from 5 to 8 it exceeds the minimum by one comparison, because the merge is not optimal for small sizes: the lower bound is never violated, as it must be, and merge sort does not exceed it by much. Remember also that "Ω(n log n)" holds only for algorithms that use comparisons exclusively; sorts that exploit the value of the keys, like counting sort, are not covered by the theorem.
Constants matter, and the notation hides them
Asymptotic notation hides the constants by construction: 100n is Θ(n) and n² is Θ(n²), but the first listing already showed that 100n is below n² only from n = 100 onwards. An asymptotically worse algorithm can therefore be better on small data, and practice confirms it: the CPython development documentation on list sorting (listsort.txt) explains that Timsort extends runs that are too short with a binary insertion sort, and that when the array is shorter than a threshold it sorts it entirely this way. There you read that tests on random data found equivalent values of minrun between 16 and 128, and the choice fell on 32. I did not measure times on this machine for a comparison between insertion and merge: the number of comparisons, by itself, does not reveal the crossover point, which depends on the cost of each step.
The lesson is that asymptotic analysis is a guide to behaviour as the input grows, not a verdict on the time of a single call. If your data have fixed, small sizes, measure. The same text by Lehman and colleagues gives the example of the matrix multiplication algorithm with O(n^2.55) operations, almost never used because it pays off only on matrices of impractical size.
The most common classes and what they mean at n = one million
From the slowest to grow to the fastest to explode, these are the classes you will meet most often. The orders of magnitude are computed assuming each operation costs 1 nanosecond: it is a working assumption to make the differences visible, not a measurement of a real machine. The listing computes the right-hand column.
import math
n = 10**6
SECONDI_ANNO = 365.25 * 24 * 3600
print("n = 10^6, one operation = 1 ns (working assumption, not a measurement)")
righe = [("log n", math.log2(n)), ("n", n), ("n log n", n * math.log2(n)), ("n^2", n**2), ("n^3", n**3)]
for nome, ops in righe:
secondi = ops * 1e-9
if secondi < 1e-3:
t = f"{secondi * 1e9:.4g} ns"
elif secondi < 1:
t = f"{secondi * 1e3:.4g} ms"
elif secondi < 86400 * 365:
t = f"{secondi / 60:.4g} min"
else:
t = f"{secondi / SECONDI_ANNO:.4g} years"
print(f" {nome:>8}: {ops:.4g} operations -> {t}")
log10_ops = n * math.log10(2)
print(f" {'2^n':>8}: 10^{log10_ops:.0f} operations -> 10^{log10_ops - 9 - math.log10(SECONDI_ANNO):.0f} years")
# Output (two runs, identical output):
# n = 10^6, one operation = 1 ns (working assumption, not a measurement)
# log n: 19.93 operations -> 19.93 ns
# n: 1e+06 operations -> 1 ms
# n log n: 1.993e+07 operations -> 19.93 ms
# n^2: 1e+12 operations -> 16.67 min
# n^3: 1e+18 operations -> 31.69 years
# 2^n: 10^301030 operations -> 10^301013 years
| Class | Name | Example | Operations | Time at 1 ns/op |
|---|---|---|---|---|
| O(log n) | Logarithmic | Binary search on a sorted array | ≈ 20 | ≈ 20 ns |
| O(n) | Linear | Scan of an array | 10⁶ | 1 ms |
| O(n log n) | Linearithmic | Merge sort (comparisons) | ≈ 2·10⁷ | ≈ 20 ms |
| O(n²) | Quadratic | Insertion sort, worst case | 10¹² | ≈ 17 minutes |
| O(n³) | Cubic | Matrix multiplication with three loops | 10¹⁸ | ≈ 32 years |
| O(2ⁿ) | Exponential | Enumeration of subsets | ≈ 10³⁰¹⁰³⁰ | ≈ 10³⁰¹⁰¹³ years |
The row that matters is the distance between O(n log n) and O(n²) at the same size: twenty milliseconds against seventeen minutes. With the same assumption, the jump from O(n³) to O(2ⁿ) is no longer comparable with anything physical: a number of years with three hundred thousand digits is not "long", it is outside any physical scale. This explains why the distinction between polynomial and exponential matters more than any constant, while between two algorithms of the same class the constants become the criterion again.
What you can do now
You can read O, Ω, Θ and o as relations between functions with their definition, and you can check a witness (c, n₀) that someone proposes to you. Above all you can avoid the three slips mentioned above, which show up everywhere: saying "Big-O is the worst case", saying "Omega is the best case", saying that an algorithm is "Θ(...)" without saying for which case. The method you take away is simple: for every statement about cost, first write the function (which algorithm, which case, which operation counted), then the bound, then count on a few sizes and check that the ratio stays within a constant.
- Big-O: upper bound of a cost function; it can be applied to the worst, the best or the average case.
- Omega Ω: lower bound; for problems it says "you cannot do better", for algorithms it says "it does not cost less than".
- Theta Θ: tight bound of a precise cost function; it does not exist for "the algorithm" if the cases have different orders.
- Constants matter on small data: the notation guides, counting and measuring decide.
The four items are the reminder to keep next to every complexity estimate you read or write, and each prevents a different mistake: confusing the bound with the case, demanding a Θ where the cases diverge, forgetting the assumption behind an O(1), trusting the class when the data are small. In the same vein, the series "Algorithms and Data Structures" continues with the complexity analysis (article 01), the sorting algorithms and linear search, binary search and hash tables.
Sources
- Lehman, Leighton, Meyer, Mathematics for Computer Science (MIT, revision of 2018-06-06), chapter 14, § 14.7 "Asymptotic Notation" - definitions of O, Ω, Θ and little o, examples on 4ⁿ and 2ⁿ, warnings about the use of the "=" sign, note on matrix multiplication; read in the PDF on 2026-11-13.
- Jeff Erickson, Algorithms (CC BY 4.0 licence), chapter 0 - the nursery-rhyme example and the advice to measure time by counting the executions of an instruction; read in the PDF on 2026-11-13.
- Python, Time complexity of operations on built-in types - costs of
x in landx in sand the average-case assumption for hash tables; consulted on 2026-11-13. - CPython, Objects/listsort.txt - use of binary insertion sort in Timsort and the choice of minrun; read on 2026-11-13.
Commenti
Caricamento commenti...
Sign in to comment