Big O notation describes the asymptotic upper bound on the growth rate of an algorithm's time or space requirements as a function of input size n, abstracting away constant factors and lower-order terms to characterise how the algorithm scales.
Big O notation describes how the running time (or memory usage) of an algorithm grows as the input size grows — it answers: if I double the input, does the work double, quadruple, or barely change?
What Big O measures
When we say an algorithm is O(n), we mean: as the input size n grows, the number of operations grows proportionally to n. Double the input, double the work. When we say O(n²), doubling the input quadruples the work. The notation describes the growth rate of the worst case — not the exact number of operations.
Big O deliberately ignores constant factors and lower-order terms. O(3n) and O(n/2) are both written as O(n) because they all grow linearly — the constant matters less than the shape of the curve as n gets large.
The main complexity classes
| Notation | Name | n=10 | n=100 | n=1,000 | Example |
|---|---|---|---|---|---|
| O(1) | Constant | 1 | 1 | 1 | Array index access |
| O(log n) | Logarithmic | 3 | 7 | 10 | Binary search |
| O(n) | Linear | 10 | 100 | 1,000 | Linear scan |
| O(n log n) | Linearithmic | 33 | 664 | 9,966 | Merge sort, heapsort |
| O(n²) | Quadratic | 100 | 10,000 | 1,000,000 | Bubble sort, insertion sort |
| O(2ⁿ) | Exponential | 1,024 | 10³² | 10³⁰¹ | Brute-force subset search |
| O(n!) | Factorial | 3.6M | 9.3×10¹ᐅ⁶ | ∞ | Brute-force TSP |
Reading complexity from code
One loop over n elements: O(n). Two nested loops over n elements: O(n²). Halving the input on each step (binary search, tree traversal): O(log n). A loop plus a halving inner loop: O(n log n). The key question: how many operations does this code perform as a function of the input size?
# O(1) — same work regardless of list size
def get_first(lst): return lst[0]
# O(n) — work grows linearly
def find_max(lst):
m = lst[0]
for x in lst: # n iterations
if x > m: m = x
return m
# O(n^2) — two nested loops
def has_duplicate(lst):
for i in range(len(lst)): # n
for j in range(i+1, len(lst)): # n
if lst[i] == lst[j]:
return True
return False
# O(log n) — input halved each step
def binary_search(lst, target):
lo, hi = 0, len(lst) - 1
while lo <= hi:
mid = (lo + hi) // 2
if lst[mid] == target: return mid
elif lst[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1Why it matters practically
At n=1,000,000: O(n) takes ~1 ms. O(n log n) takes ~20 ms. O(n²) takes ~17 minutes. O(2ⁿ) is longer than the age of the universe. The choice of algorithm determines whether a program is usable or not at scale.
Formal definition
f(n) = O(g(n)) means: there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c⋅g(n) for all n ≥ n₀. Informally: f grows no faster than g past some threshold. This is an upper bound. The formal definition comes from Bachmann (1894) and Landau (1909).
Related notations: Ω(g) (lower bound — grows at least as fast as g), Θ(g) (tight bound — grows at the same rate as g), o(g) (strictly slower than g). Big O is most commonly used in CS because we care most about worst-case upper bounds.
Best, average, and worst case
An algorithm can have different complexities for different inputs. Quicksort: best case O(n log n) (balanced pivot every time), average case O(n log n) (random input), worst case O(n²) (already-sorted input with naive pivot). When someone says "quicksort is O(n log n)," they usually mean average case. When someone says "merge sort is O(n log n)," they mean all cases — it is always Θ(n log n).
Space complexity
Big O also describes memory usage. An in-place sorting algorithm like heapsort uses O(1) extra space. Merge sort uses O(n) extra space (for the temporary merge buffer). A recursive function with depth d uses O(d) stack space. A hash table storing n entries uses O(n) space plus overhead for load factor.
Amortised complexity
Some operations are occasionally expensive but cheap on average. A dynamic array append is O(n) in the worst case (when it triggers a resize) but O(1) amortised — averaged over a sequence of n appends, the total cost is O(n), so O(1) per operation. Amortised analysis accounts for rare expensive operations by spreading their cost over many cheap ones.
The formal definitions: O, Ω, Θ
O (Big O): f(n) = O(g(n)) iff ∃ c > 0, n₀ > 0 such that f(n) ≤ c⋅g(n) ∀ n ≥ n₀. Upper bound.
Ω (Big Omega): f(n) = Ω(g(n)) iff ∃ c > 0, n₀ > 0 such that f(n) ≥ c⋅g(n) ∀ n ≥ n₀. Lower bound.
Θ (Big Theta): f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)). Tight bound — grows at exactly the same rate as g up to a constant factor.
The master theorem
For divide-and-conquer recurrences T(n) = aT(n/b) + f(n), the master theorem gives a closed-form solution. Three cases based on comparing f(n) with nlogba:
Case 1: if f(n) = O(nlogba − ε) for some ε > 0, then T(n) = Θ(nlogba).
Case 2: if f(n) = Θ(nlogba), then T(n) = Θ(nlogba log n).
Case 3: if f(n) = Ω(nlogba + ε), then T(n) = Θ(f(n)) (with regularity condition).
Merge sort: T(n) = 2T(n/2) + Θ(n). Here a=2, b=2, f(n)=n, nlog22=n. Case 2: T(n) = Θ(n log n).
Cormen, T. H. et al. (2022). CLRS (4th ed.), Ch. 3 — Characterising running times (formal O/Ω/Θ definitions); Ch. 4.5 — Master theorem. Knuth, D. E. (1976). "Big Omicron and Big Omega and Big Theta." ACM SIGACT News 8(2). Bachmann, P. (1894). Die analytische Zahlentheorie.