Big-O describes how an algorithm's cost grows as the input grows, ignoring constant factors and lower-order terms. It is the language for comparing approaches on paper, before a line of code runs and before hardware muddies the picture. The point is to capture the shape of the growth, not an exact operation count, because that shape is what decides whether a method survives a hundredfold larger input.
Formally, $f(n) = O(g(n))$ means there are constants $c > 0$ and $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$. So $O$ is an asymptotic upper bound up to a constant; its companions are $\Omega$ for a lower bound and $\Theta$ when the same function bounds from both sides (a tight estimate). In casual use people say "O" but usually mean the tight $\Theta$.
Why asymptotics instead of benchmarks
Constants depend on the machine, language, and compiler, none of which are intrinsic to the algorithm, whereas the growth exponent is. That is why an $O(n)$ method eventually beats an $O(n^2)$ one no matter how slow its constant: pick $n$ large enough and the quadratic always loses. Benchmarks still matter for choosing among algorithms of the same class, but they cannot tell you which class you are in.
Reading complexity off code
A single pass over the input is $O(n)$; nested loops over the input multiply, giving $O(n^2)$; sequential blocks add, and the larger term dominates. Recursion is handled with a recurrence. Divide-and-conquer that makes $a$ calls on inputs of size $n/b$ with $f(n)$ work to split and combine satisfies
$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n),$$
and the master theorem reads off the answer by comparing $f(n)$ with $n^{\log_b a}$: merge sort ($a=b=2$, $f=O(n)$) gives $T(n)=\Theta(n\log n)$, while binary search ($a=1$, $b=2$, $f=O(1)$) gives $T(n)=\Theta(\log n)$.
The classes you actually meet
- $O(1)$ constant: a hash lookup. The cost does not grow with $n$.
- $O(\log n)$ logarithmic: binary search. Each step throws away a constant fraction, so the count is how many times you can halve $n$.
- $O(n)$ linear: one scan.
- $O(n\log n)$: comparison sorting and most divide-and-conquer.
- $O(n^2)$ quadratic: checking all pairs.
- $O(2^n)$ and $O(n!)$: enumerating all subsets or all orderings; only feasible for tiny $n$.
Space, amortized, and average cost
The same counting applies to extra memory, and the recursion stack counts: a depth-$d$ recursion uses $O(d)$ stack even if it allocates nothing else. Two refinements matter in practice. Amortized analysis averages cost over a sequence, which is why appending to a dynamic array is $O(1)$ amortized even though an occasional resize is $O(n)$. Average-case assumes a distribution of inputs, which is how quicksort is $O(n\log n)$ on average despite an $O(n^2)$ worst case.
Step by step: analyzing an algorithm
- Identify the input size $n$ that drives the work.
- Count the dominant operation as a function of $n$.
- Drop constant factors and lower-order terms.
- For recursion, write the recurrence and apply the master theorem.
- Repeat the count for extra memory to get the space complexity.
# O(n) time, O(n) space: one pass with a hash set
def has_duplicate_seen(a):
seen = set()
for x in a:
if x in seen:
return True
seen.add(x)
return False
# O(n^2) time, O(1) extra space: check every pair
def has_duplicate_pairs(a):
for i in range(len(a)):
for j in range(i + 1, len(a)):
if a[i] == a[j]:
return True
return False
Complexity (time and space)
The first function is $O(n)$ time and $O(n)$ memory; the second is $O(n^2)$ time and $O(1)$ memory. They compute the same answer, so they are a clean illustration of a time-space trade-off: the hash set spends memory to avoid the quadratic scan.
Worked example
Both detect the repeated 1, but only the first stays linear as the list grows:
print(has_duplicate_seen([3, 1, 4, 1, 5])) # True (linear, one pass)
print(has_duplicate_pairs([3, 1, 4, 1, 5])) # True (quadratic, all pairs)
Follow-up questions
- Why drop constant factors? They depend on machine, language, and compiler, not on the algorithm; the growth rate is the intrinsic, machine-independent property.
- Difference between O, Theta, and Omega? O is an upper bound, Omega a lower bound, and Theta a tight bound when the same function bounds both sides.
- Does the recursion stack count as space? Yes; a recursion of depth $d$ uses $O(d)$ stack memory even with no other allocation.
- What does amortized O(1) mean? The average cost per operation over a long sequence is constant, even if individual operations (like a dynamic-array resize) are occasionally $O(n)$.
- How do you analyze divide-and-conquer? Write the recurrence $T(n)=aT(n/b)+f(n)$ and apply the master theorem, comparing $f(n)$ with $n^{\log_b a}$.
References
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms (CLRS, 4th ed.).
- Knuth, The Art of Computer Programming, Vol. 3.
- Skiena, The Algorithm Design Manual (3rd ed.).