Two programs can solve the same problem and give the same result, yet one takes an instant and the other several minutes. With a hundred items the difference goes unnoticed; with a million it becomes enormous. Big O notation is the tool computer scientists use to describe this difference precisely, regardless of the computer, the language or the skill of whoever wrote the code.
What it measures
Big O notation describes how the work of an algorithm grows as the size of the input grows, usually written as n. It does not say how many seconds a program takes: it says how the time changes when the data doubles, increases tenfold or reaches the millions.
That is why it focuses on behaviour for large n and ignores two things:
- constants: an algorithm doing 3n operations and one doing 100n are both O(n);
- lower-order terms: n² + 50n + 7 is O(n²), because for large n the n² term dominates everything else.
It looks like a brutal simplification, and it is. But that very simplification is what makes it useful: it lets you compare ideas, not details.
The most common classes
| Notation | Name | Typical example | With n = 1,000,000 |
|---|---|---|---|
| O(1) | Constant | Accessing an array element by index | 1 operation |
| O(log n) | Logarithmic | Binary search in a sorted list | about 20 operations |
| O(n) | Linear | Scanning a list to find the maximum | 1 million |
| O(n log n) | Linearithmic | Efficient sorting algorithms | about 20 million |
| O(n²) | Quadratic | Comparing every element with every other | a trillion |
| O(2ⁿ) | Exponential | Trying every subset of a set | impractical |
The last column is indicative, but it makes the point: the difference between O(n log n) and O(n²) with a million elements is the difference between an instant operation and one that can take hours.
Examples in code
The simplest way to estimate complexity is to look at the loops.
def contains(items, value):
for item in items: # n iterations
if item == value:
return True
return False
A loop that goes through the input once: O(n).
def has_duplicates(items):
for i in range(len(items)):
for j in range(i + 1, len(items)): # loop inside a loop
if items[i] == items[j]:
return True
return False
Two nested loops over the same input: O(n²). The same problem can be solved in O(n) by using a set, which offers lookups in average constant time:
def has_duplicates(items):
seen = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
This is the most important practical use of Big O notation: recognising when a quadratic algorithm can become linear with a different data structure.
The logarithm, without fear
O(log n) scares people who dislike maths, but the idea is intuitive: a logarithmic algorithm halves the problem at every step. Looking up a name in a sorted directory by opening it in the middle, then in the middle of the right half, and so on: with a million names about twenty steps are enough, because 2 to the power of 20 already exceeds a million. Doubling the data adds just one step.
Worst, average and best case
When people say an algorithm is O(n), they usually mean the worst case. The contains function may find the value at the first element (best case) or not find it at all after scanning everything (worst case). Some algorithms behave very differently across cases: quicksort, for example, is O(n log n) on average but O(n²) in the worst case. Knowing this distinction avoids surprises when the data is not what you expected.
Not only time: space
The same notation is used for memory. The second version of has_duplicates is faster, but uses O(n) extra memory for the set, while the first uses O(1). Space is often traded for time, and it is a deliberate choice to make based on the context.
When complexity is not everything
Big O notation is an excellent reasoning tool, but it does not replace real measurement. With small inputs, a simple O(n²) algorithm can be faster than a complex O(n log n) one, because the neglected constants matter. And many real performance problems depend on something else: disk access, network calls, database queries repeated inside a loop. The practical rule: use complexity to choose the approach, then measure with a profiler before optimising.
In short
- Big O notation describes how an algorithm's cost grows as the input grows.
- It ignores constants and lower-order terms, to compare ideas rather than details.
- Nested loops over the same input suggest O(n²); a suitable data structure often brings it back to O(n).
- O(log n) means halving the problem at every step.
- Use complexity to reason, but always measure before optimising.
