Big O Notation
Overview
Big O notation describes how the effort of an algorithm grows with its input. Instead of a time in seconds, it states the shape of that growth.
The input size is called n: it represents the number of elements in a list, characters in a string or rows in a table. Every complexity class answers the question: what happens to the number of steps when n doubles?
| Notation | Name | When n doubles, the effort ... | Example |
|---|---|---|---|
| O(1) | Constant | stays the same | Array access by index |
| O(log n) | Logarithmic | grows by one step | Binary search |
| O(n) | Linear | doubles | Linear search |
| O(n log n) | Linearithmic | slightly more than doubles | Merge sort |
| O(n²) | Quadratic | quadruples | Bubble sort, nested loops over the same list |
| O(2ⁿ) | Exponential | squares | Trying every subset of a set |
For O(2ⁿ), a single additional element already doubles the effort.
Growth in Numbers
Number of steps each complexity class needs for an input of n elements (log to base 2, rounded):
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 1 | 7 | 100 | 664 | 10,000 | ≈ 1.3 x 10³⁰ |
| 1,000 | 1 | 10 | 1,000 | 9,966 | 1,000,000 | ≈ 1.1 x 10³⁰¹ |
| 1,000,000 | 1 | 20 | 1,000,000 | ≈ 2 x 10⁷ | 10¹² | ≈ 10³⁰¹⁰³⁰ |
At one microsecond per step and one million elements, an O(log n) algorithm needs 20 µs, an O(n) algorithm one second, an O(n log n) algorithm about 20 seconds and an O(n²) algorithm 10⁶ seconds, which is about 11.6 days.
Formal Definition
f(n) is the number of steps an algorithm needs, g(n) a simple comparison function such as n or n². f(n) is in O(g(n)) if, from a certain input size onwards, f grows at most as fast as g multiplied by a fixed factor.
Formally: there are a constant c > 0 and a threshold n₀ such that f(n) ≤ c x g(n) holds for all n ≥ n₀.
Example: f(n) = 3n + 5 is in O(n). With c = 4 and n₀ = 5, 3n + 5 ≤ 4n holds for all n ≥ 5.
- Constant factors are absorbed by c.
3n,n / 2and100nare all in O(n). - The behaviour below n₀ is irrelevant, as Big O only describes large inputs.
- O is an upper bound. Strictly, binary search is also in O(n) and in O(n²). In practice the smallest fitting class is given.
- The lower bound is written Ω (Omega). A bound that is both upper and lower bound is written Θ (Theta).
Determining the Complexity Class
The complexity class is determined by counting the most frequent operation, usually a comparison or an assignment in the innermost loop, as a function of n and simplifying the result.
Single Statements: O(1)
Assignments, arithmetic, comparisons, array access by index and RETURN run a fixed number of times that does not depend on n.
first = list[0]
sum = a + b
Loop over the Input: O(n)
FOR i = 0 TO n - 1
sum = sum + list[i]
END FOR
The FOR runs n times. A loop that runs n / 2 or 2n times is O(n) as well.
Nested Loops: Multiply
The iteration counts of nested loops are multiplied. When both loops run over the input, this gives n x n steps and O(n²):
FOR i = 0 TO n - 1
FOR j = 0 TO n - 1
...
END FOR
END FOR
When the inner loop has a fixed number of iterations, this gives n x 7 = 7n steps and therefore O(n):
FOR i = 0 TO n - 1
FOR day = 1 TO 7 // 7 iterations, independent of n
...
END FOR
END FOR
Consecutive Blocks: Keep the Largest Term
When code blocks run one after the other, their step counts are added. Only the fastest-growing part of the sum determines the class:
FOR i = 0 TO n - 1 // n steps
...
END FOR
FOR i = 0 TO n - 1 // n x n steps
FOR j = 0 TO n - 1
...
END FOR
END FOR
n + n² steps give O(n²). The larger n gets, the less the smaller part matters.
Halving: O(log n)
When every step halves the remaining problem, the number of steps equals the number of times n can be halved until one element remains. That number is log₂ n. Big O omits the base, because log₂ n and log₁₀ n differ only by a constant factor.
1,000,000 => 500,000 => 250,000 => ... => 1 20 halvings
Binary search works this way on a sorted list:
low = 0
high = n - 1
WHILE low <= high
mid = (low + high) DIV 2
IF list[mid] == target THEN
RETURN mid
ELSE IF list[mid] < target THEN
low = mid + 1
ELSE
high = mid - 1
END IF
END WHILE
RETURN -1
Divide and Conquer: O(n log n)
Merge sort halves the list until single elements remain. That gives log n levels. On every level all n elements are merged once. log n levels x n steps per level gives O(n log n).
Two Inputs: Two Variables
When an algorithm works on two independent inputs of sizes n and m, both appear in the result:
FOR EACH customer IN customers // n customers
FOR EACH product IN products // m products
...
END FOR
END FOR
The nested loops give n x m steps and therefore O(n x m). Two loops one after the other give O(n + m). Unlike n + n², neither term can be dropped, because it is unknown which of the two inputs is larger.
Best, Average and Worst Case
The same algorithm needs a different number of steps depending on the input:
- Best case: The most favourable input. For linear search, this is a value at the first position, found after one comparison. The best case describes a lucky coincidence and says little about typical behaviour.
- Average case: The expected effort over all inputs. For linear search, this is n / 2 comparisons, which is O(n).
- Worst case: The most unfavourable input. For linear search, this is a value at the last position or a missing value, which costs n comparisons. The worst case is a guarantee that the algorithm never exceeds.
A complexity stated without a qualifier refers to the worst case. Average and worst case can differ drastically in their class: Quicksort needs O(n log n) on average, but O(n²) when the pivot element is always the smallest or largest value.
Space Complexity
The same notation describes the memory an algorithm needs in addition to its input.
- O(1): A fixed number of variables, e.g. bubble sort, which swaps elements within the list (in place).
- O(log n): Recursion that halves the problem keeps log n calls on the stack at the same time.
- O(n): An auxiliary structure that grows with the input, e.g. the temporary list in merge sort or a set of all values seen.
Time and memory can often be traded against each other. The worked example shows such a trade.
Classes of Common Algorithms
Searching
| Algorithm | Best case | Average case | Worst case | Extra space | Precondition |
|---|---|---|---|---|---|
| Linear search | O(1) | O(n) | O(n) | O(1) | None |
| Binary search | O(1) | O(log n) | O(log n) | O(1) | Sorted data with access by index |
Sorting
| Algorithm | Best case | Average case | Worst case | Extra space | Stable |
|---|---|---|---|---|---|
| Bubble sort | O(n)¹ | O(n²) | O(n²) | O(1) | Yes |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion sort | O(n)² | O(n²) | O(n²) | O(1) | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
¹ Only with an early exit that stops after a pass without any swap. Without it, bubble sort always needs O(n²).
² For an already sorted list, every element is compared with its predecessor once and stays in place.
A sort is stable when elements with equal keys keep their original order. The key is the value the list is sorted by. A list of people already sorted by name and then sorted stably by age keeps people of the same age in alphabetical order.
A sort that only compares two elements at a time needs at least about n log n comparisons in the worst case. Merge sort therefore reaches the best possible class for comparison-based sorting. Only sorts that use the values directly, such as counting sort for small integers, can be faster.
Data Structures
| Operation | Array | Linked list | Hash table |
|---|---|---|---|
| Access to the element at i | O(1) | O(n)¹ | Not applicable² |
| Search for a value or key | O(n), sorted O(log n) | O(n) | O(1) average by key³ |
| Insert at the beginning | O(n)⁴ | O(1)⁵ | Not applicable² |
¹ Each element only knows its successor, so the list is walked from the start.
² A hash table has no order of its elements, so there is no position.
³ A hash function computes the storage location, the bucket, directly from the key. When many keys land in the same bucket, they are searched one by one, and the lookup degrades to O(n) in the worst case.
⁴ All n existing elements are shifted one position to the right.
⁵ Only one reference is redirected.
Worked Example: Finding Duplicates
A function checks whether a list contains any value twice.
Variant 1: Compare Every Pair
FUNCTION hasDuplicates(list)
n = LENGTH(list)
FOR i = 0 TO n - 2
FOR j = i + 1 TO n - 1
IF list[i] == list[j] THEN
RETURN true
END IF
END FOR
END FOR
RETURN false
END FUNCTION
The worst case is a list without duplicates, so every pair is compared:
i = 0 n - 1 comparisons
i = 1 n - 2 comparisons
...
i = n - 2 1 comparison
Total: (n - 1) + (n - 2) + ... + 1 = n x (n - 1) / 2 = 0.5n² - 0.5n
n = 5: 4 + 3 + 2 + 1 = 5 x 4 / 2 = 10
Dropping the smaller term 0.5n and the constant factor 0.5 leaves O(n²). The inner loop gets shorter on every pass, but on average it still runs over half the list. At n = 1,000 this is 499,500 comparisons, at n = 2,000 it is 1,999,000, which is four times as many.
Variant 2: Sort First, Then Compare Neighbours
FUNCTION hasDuplicates(list)
n = LENGTH(list)
sort(list) // O(n log n)
FOR i = 0 TO n - 2 // O(n)
IF list[i] == list[i + 1] THEN
RETURN true
END IF
END FOR
RETURN false
END FUNCTION
After sorting, equal values sit next to each other, and one pass over neighbouring pairs is enough. O(n log n) + O(n) gives O(n log n). Unless the function sorts a copy, it changes the order of the passed list. A copy costs O(n) memory.
Variant 3: Remember Seen Values
FUNCTION hasDuplicates(list)
seen = empty set
FOR EACH value IN list // n iterations
IF seen CONTAINS value THEN // O(1) average
RETURN true
END IF
ADD value TO seen // O(1) average
END FOR
RETURN false
END FUNCTION
A hash-based set answers "contains" in constant time on average. n iterations with O(1) each give O(n). The set costs O(n) additional memory.
Comparison
| Variant | Time | Extra space | Steps for n = 1,000,000 |
|---|---|---|---|
| 1: Every pair | O(n²) | O(1) | ≈ 5 x 10¹¹ |
| 2: Sort first | O(n log n) | O(1), with a copy O(n) | ≈ 2 x 10⁷ |
| 3: Set | O(n) | O(n) | ≈ 10⁶ |
What this example shows:
- Only a different approach improves the class. Optimising the inner loop of variant 1 changes the constant factor alone.
- Variant 3 buys its speed with memory.
Common Mistakes
- Every nested loop counted as O(n²): The class depends on how often each loop runs. An inner loop with a fixed number of iterations, e.g. over the seven days of a week, only multiplies by a constant factor, and the result stays O(n).
- Two different inputs written as n: A loop over n customers nested with a loop over m products is O(n x m). O(n²) assumes both inputs have the same size and hides which of them drives the effort.
- Constants and smaller terms kept: O(2n + 5) and O(n² + n) are formally correct but not simplified. The classes are O(n) and O(n²) respectively, because constants and smaller terms have no influence on the growth for large n.
- Big O read as a runtime in seconds: The notation hides constant factors, so an O(n²) algorithm can be faster than an O(n log n) algorithm for small n. Insertion sort beats merge sort on short lists, which is why practical sort implementations such as Timsort use insertion sort for short sections.
- Binary search on unsorted data: O(log n) only holds for sorted data with access by index. Sorting beforehand costs O(n log n) and only pays off when the same data is searched many times.
- log n confused with n log n: O(log n) grows slower than linear and needs far fewer steps than there are elements. O(n log n) grows faster than linear and performs log n steps for every element.
- Best case given as the complexity: The best case of linear search is O(1) and says nothing about typical inputs. A complexity without a qualifier refers to the worst case.