Skip to content

Big O — algorithm complexity

Big O is a notation: a way to describe how an algorithm’s work grows as the amount of data increases.

Two ways to process ten players may both seem fast. At a thousand players, one may need a thousand checks while the other needs a million. Complexity helps explain that difference in growth; a benchmark measures the actual running time.

Start with the interactive examples: change the amount of data and watch how many steps each algorithm takes. Then use what you have seen to estimate the complexity of code yourself.

What does N mean?

N is the size of the data an algorithm works with. For a list or an array, it is simply the number of elements:

We use a letter because the same algorithm can work with different amounts of data. Today a list might have 10 entries; tomorrow it might have 1,000. We can describe both with N.

N tells us how much data there is. The number of steps depends on what we do with it. Reading the first entry in a list of 100 players takes one lookup; checking every player takes 100 checks. Try changing N in the examples below and watch what happens to the work.

O(1)

The operation count stays constant as the input grows. The required position is already known, so the algorithm does not visit the other elements.

O(1) — direct access by index

Step 0
Operations: 0
Pseudocode

O(log N)

Each step roughly halves the search area. Doubling the number of elements adds about one step, as in binary search or a path through a balanced tree.

O(log N) — binary search

Step 0
Operations: 0
Pseudocode

O(N)

The algorithm visits elements one at a time. Twice as much data means roughly twice as much work. A search can finish early, but its worst case needs a full scan.

O(N) — search from left to right

Step 0
Operations: 0
Pseudocode

O(N log N)

Each of N objects performs a logarithmic search or insertion. Compare repeated binary searches with building a results table using a tree.

O(N log N) — N objects, each with a log N search

Step 0
Operations: 0
Pseudocode

O(N²)

Each element triggers another full scan, producing two nested loops. Compare examining every pair with traversing a square board.

O(N²) — fix A and move B through the entire array

Step 0
Operations: 0
Pseudocode

O(2ⁿ)

All equipment subsets

Pseudocode
Visit(i):
    if i == N: CountVariant(); return
    Choose(i, false); Visit(i + 1)
    Choose(i, true);  Visit(i + 1)

O(N!)

All permutations of a lock code

Pseudocode
Visit(depth):
    if depth == N: CountVariant(); return
    for each unused symbol:
        Use(symbol); Visit(depth + 1); Undo(symbol)

How work grows

232

From counting operations to Big O

Start with three questions: what can grow, which operation are we counting, and which inputs are we considering?

  1. Define the input size. For a list of players, N is the number of players. For an array, it is the number of elements. Start by stating what you are counting.
  2. Choose a unit of work. For example, count the comparisons when searching for a number, or the writes when copying an array.
  3. Count how often the work happens. Include repeated work inside helper functions. A single line can scan or copy an entire array.
  4. Keep the terms that determine growth. If a count is 3N + 20, we write O(N). If it is N² + N, we write O(N²). Constant factors and smaller terms still affect actual performance, especially on small inputs.

Recognizing complexity in code

O(1) Direct access. The amount of data does not change the number of steps.
O(log N) Each step discards a large share of the candidates: binary search or one path through a balanced tree.
O(N) One full pass. Typically i++, foreach, or checking every element.
O(N log N) N objects × one O(log N) operation each, such as binary search or a path through a balanced tree.
O(N²) Two nested passes. Every element with every element. An N × N table.
O(2ⁿ)Two choices per object: enumerate all subsets.
O(N!)Enumerate all orders: each position leaves one fewer choice.

Use the patterns above as clues, then count the work. Nesting alone does not determine complexity. In the examples below, N is the array length and each process call takes O(1) work.

Two nested loops, but only O(N) work
for i from 0 to N - 1:
    for repeat from 1 to 10:
        process(values[i])

The inner loop always runs ten times. Total work is 10N, so the bound is O(N), not O(N²).

A logarithmic inner loop gives O(N log N)
for i from 0 to N - 1:
    j = 1
    while j < N:
        process(values[i])
        j = j * 2

Each outer iteration starts j at 1. It doubles until it reaches or exceeds N, so the inner loop runs ⌈log₂ N⌉ times. Repeating it N times gives O(N log N). The ceiling means rounding up.

An inner loop whose work is shared across iterations
j = 0
for i from 0 to N - 1:
    while j < N and values[j] <= values[i]:
        j = j + 1

Assume values is sorted in ascending order. Unlike the previous example, j is never reset. It advances at most N times over the entire algorithm, and the outer loop runs N times. Total work is O(N), including the boundary checks.

Different inner lengths: add them before simplifying
for i from 0 to N - 1:
    for j from i + 1 to N - 1:
        checkPair(values[i], values[j])

This checks each pair of different elements once. The count is (N − 1) + (N − 2) + … + 1 = N(N − 1) / 2. It avoids self-pairs and duplicate checks, but the growth is still O(N²).

When two independent sizes appear, keep both: checking every inventory item against every storage slot costs O(NM). Replace this with O(N²) only when the relationship between the sizes justifies it.

Adding and multiplying complexities

When stages run one after another, add their costs (+). When one piece of work repeats inside another, multiply (×). Explore both with storage examples, then simplify the resulting bound.

Find an item

Pseudocode

First add the costs of all stages, then simplify. O(N + M) cannot become O(N) unless the relationship between N and M is known. If inner work varies by step, add those amounts instead of automatically multiplying sizes.

How memory use grows

One task: reverse an array's element order. Both methods require O(N) work but use different amounts of memory. Count space beyond the input array, including the result. Elements are fixed-size numbers.

Reverse in place

Code for this step

What the notation tells us

Big O is an upper bound on growth. Beyond some input size, the work stays below a constant multiple of the chosen function. For example, 3N + 20 ≤ 4N whenever N ≥ 20, so 3N + 20 is O(N).

A linear count is also O(N²), but that looser bound tells us less. We aim for an informative bound. Θ (“theta”) describes a tight order of growth; Ω (“omega”) gives a lower bound. These symbols do not themselves mean best, average, or worst case: those are separate choices about which inputs to analyze.

The meaning of N matters. A grid with N rows and N columns contains N² cells. Visiting every cell is quadratic in the side length, but linear in the number of cells. The algorithm is the same; the quantity used to describe its input size has changed.

One line of code can do more than one unit of work. In these examples, reading, comparing, or writing fixed-size values takes constant work. Comparing long strings or copying an array may require a full pass through the data.

Why is the base of the logarithm usually omitted?

Halving a search range gives log₂ N levels; reducing it to one tenth gives log₁₀ N. The two differ by a constant factor, so both belong to O(log N). Removing just one candidate per step, however, takes O(N) steps in the worst case.

Amortized cost

One push_back can mean moving every existing element. While space remains, an append costs one write. When the block is full, move the old elements into a new one.

Bar height is the number of moves and writes for one append. This models operations, not elapsed time.

Code for this step
Why amortized O(1)?

With capacity doubling, N appends require fewer than 2N moves and exactly N new writes. That is fewer than 3N units of work: the average cost across the whole sequence is bounded by a constant. An individual append that expands the array requires O(N).

Doubling is an assumption of this model, not a guaranteed std::vector growth factor. Moving a scalar element or writing one counts as one operation; allocator and destructor work is not modeled. This is amortization across a sequence, not an average case over random inputs.