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

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 runs ++steps once for every pair of i and j:

#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 a hundred times, and the number of steps grew ten thousand times.

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 its complexity is O(n²). Constant factors and smaller terms are dropped: 3n + 5 steps is O(n), and 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.

Reading it from code

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²).

An inner loop often starts at i + 1 so that no pair is compared twice. It gets shorter, but in total it runs n(n−1)/2 times, so the complexity stays O(n²). If a loop looks up a std::map key on every step, the costs multiply: 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).

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.