Skip to main content

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?

NotationNameWhen n doubles, the effort ...Example
O(1)Constantstays the sameArray access by index
O(log n)Logarithmicgrows by one stepBinary search
O(n)LineardoublesLinear search
O(n log n)Linearithmicslightly more than doublesMerge sort
O(n²)QuadraticquadruplesBubble sort, nested loops over the same list
O(2ⁿ)ExponentialsquaresTrying 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):

nO(1)O(log n)O(n)O(n log n)O(n²)O(2ⁿ)
101310331001,024
1001710066410,000≈ 1.3 x 10³⁰
1,0001101,0009,9661,000,000≈ 1.1 x 10³⁰¹
1,000,0001201,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 / 2 and 100n are 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​

AlgorithmBest caseAverage caseWorst caseExtra spacePrecondition
Linear searchO(1)O(n)O(n)O(1)None
Binary searchO(1)O(log n)O(log n)O(1)Sorted data with access by index

Sorting​

AlgorithmBest caseAverage caseWorst caseExtra spaceStable
Bubble sortO(n)¹O(n²)O(n²)O(1)Yes
Selection sortO(n²)O(n²)O(n²)O(1)No
Insertion sortO(n)²O(n²)O(n²)O(1)Yes
Merge sortO(n log n)O(n log n)O(n log n)O(n)Yes
QuicksortO(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​

OperationArrayLinked listHash table
Access to the element at iO(1)O(n)¹Not applicable²
Search for a value or keyO(n), sorted O(log n)O(n)O(1) average by key³
Insert at the beginningO(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​

VariantTimeExtra spaceSteps for n = 1,000,000
1: Every pairO(n²)O(1)≈ 5 x 10¹¹
2: Sort firstO(n log n)O(1), with a copy O(n)≈ 2 x 10⁷
3: SetO(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​

  1. 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).
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.