Complexity: O(1), O(n), O(n log n)

Picture a tiler laying a square floor. Each row has n tiles, and there are n rows, so the whole floor takes n · n tiles. A room 10 tiles wide needs 100 tiles, and a room 1000 tiles wide needs a million. The side grew 100 times, and the work grew 10,000 times.

Programs grow the same way. Two functions can give the same answer, but on a large vector one takes a split second and the other hours. Counting the steps shows the difference. The count_steps function lays one "tile", ++steps, for every pair of i and j: the outer loop walks the rows, and the inner loop walks the tiles in a row.

#include <iostream>

int count_steps(int n) {
    int steps = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ++steps;
        }
    }
    return steps;
}

int main() {
    std::cout << count_steps(10) << ' ' << count_steps(1000) << '\n';  // 100 1000000
}

The input grew 100 times, and the number of steps grew 10,000 times, as with the tiler's work.

This is where the analogy stops: real program steps do not all take the same time, the way tiles do. Complexity does not say how many seconds the work takes. It says how many times the work grows when the data grows.

The O(…) notation

The time complexity of an algorithm describes how its number of steps grows with the input size n. It is written in Big-O notation: count_steps makes n² steps, so the complexity of this function is O(n²).

Constant factors and smaller terms are dropped:

• 3n + 5 steps is O(n);
• n²/2 steps is O(n²).

For large n they barely change how the count grows.

Complexity is usually stated for the worst case, the input on which the algorithm does the most steps. In the worst case, a search that stops at the first match finds nothing and checks all n elements. So its complexity is O(n), even though it sometimes finishes after the first step.

The table below uses log n: how many times n can be halved before 1 is left. For a million that is about 20.

Reading it from code

Complexity can be read straight from the loops:

• one loop over n elements is O(n);
• nested loops multiply their step counts: n times n is O(n²);
• loops that run one after another add up, and the larger term remains: O(n) + O(n²) is O(n²);
• a loop that looks up a std::map key on every step multiplies the costs: n times log n is O(n log n);
• a loop that halves n on every step makes about log₂ n steps, which is O(log n).

An inner loop often starts at i + 1 so that no pair is compared twice. The tiler then lays only half the square, but that is still n(n−1)/2 steps in total, so the complexity stays O(n²). Interviewers like to ask "what is the complexity of this code?".

Common mistake

A vector is processed one element at a time, and the first element is erased each time:

std::vector<int> v{3, 1, 2};
while (!v.empty()) {
    std::cout << v[0] << ' ';
    v.erase(v.begin());  // ✗
}

The program prints the right result, but on a large vector it is slow. The loop looks like O(n), yet erase shifts every remaining element one place to the left. For n elements that is n − 1, n − 2, … shifts, O(n²) in total. Walk the vector with a range-for loop instead: that is O(n), and nothing has to be erased.

Key points

• Complexity says how many times the work grows when the data grows.
• Constant factors and smaller terms are dropped, and complexity is stated for the worst case.
• Nested loops multiply their steps; loops in a row add up.
• Erasing from the front of a vector inside a loop turns O(n) into O(n²).