Big O — algorithm complexity

Big O describes how an algorithm’s operation count grows as its input grows.

It helps compare ways to solve the same problem and choose an algorithm for the expected amount of data. For example, processing ten players may be quick with either approach, while processing a thousand can require very different numbers of checks. Big O helps predict how that work grows; actual execution time is measured separately.

Interactive examples explore complexity classes, from accessing one element to enumerating every subset and order. We follow the operations an algorithm performs and why their number depends on the size of the problem.

Identify complexity Compare complexities

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.

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.

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.

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.

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.

Step 0

Operations: 0

Pseudocode

O(2ⁿ)

Pseudocode

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

O(N!)

Pseudocode

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

Recognising 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.

How work grows

Input size — N = 16

232

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.

N M

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

Elements N

Code for this step

Amortized cost

One push_back. Sometimes a whole move. While space remains, an append costs one write. When the block is full, move the old elements into a new one.

Appends

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.