Counting the work you actually do

The previous chapter turned a constraint into a budget. This one is the other half: given code, how many operations does it actually perform?

That question is harder than it looks, because the expensive parts of a C++ loop are frequently the parts that are not written as loops. v.erase(v.begin()) is one short line and O(n) work.

The doubling test

You do not have to be able to analyse code to measure it. Double the input and see what happens to the time.

#include <chrono>
#include <cstdio>

template <class T>
inline void keep(const T& value) { asm volatile("" : : "r,m"(value) : "memory"); }

int main() {
    for (int n : {500, 1000, 2000, 4000}) {
        auto start = std::chrono::steady_clock::now();
        long long count = 0;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j) count += i ^ j;
        double ms = std::chrono::duration<double, std::milli>(
            std::chrono::steady_clock::now() - start).count();
        keep(count);
        std::printf("n = %5d   %8.2f ms\n", n, ms);
    }
}

Each doubling of n multiplies the time by about four. That is the signature of O(n²), and you can read the exponent straight off the ratio:

This is the most useful debugging tool in this part of the book. When a solution times out and you are not sure why, run it on inputs of 1,000 and 2,000 and look at the ratio. A 4× jump says you have a quadratic you did not intend.

Counting loops

The rules are short.

Sequential loops add; nested loops multiply. Two loops one after another are O(n + m); one inside the other is O(n · m).

A dependent inner bound halves it, and halving does not change the class.

for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)   // n(n-1)/2 iterations

That is n²/2, which is O(n²). The constant matters for whether you fit in the limit; it does not change the complexity, and both facts are worth holding at once.

A loop whose index multiplies is logarithmic.

for (int i = 1; i <= n; i *= 2)       // log2(n) iterations

Two pointers that only move forward are linear, however nested they look.

int j = 0;
for (int i = 0; i < n; ++i)
    while (j < n && condition(i, j)) ++j;    // O(n) total, not O(n^2)

j never decreases and never exceeds n, so the inner loop’s body runs at most n times in total across all iterations of the outer one. Counting the total work rather than the worst case of a single iteration is what tells you this, and it is the whole idea behind the two-pointer technique in Chapter 10.6.

Amortised: push_back is O(1), sometimes

std::vector::push_back occasionally reallocates and copies everything. That single call is O(n). Yet pushing n elements is O(n) in total, not O(n²).

#include <cstdio>
#include <vector>

int main() {
    std::vector<int> values;
    std::size_t previous = 0;
    int reallocations = 0;

    for (int i = 0; i < 1'000'000; ++i) {
        values.push_back(i);
        if (values.capacity() != previous) {
            previous = values.capacity();
            ++reallocations;
        }
    }

    std::printf("1,000,000 pushes caused %d reallocations\n", reallocations);
    std::printf("final capacity: %zu (2^20 is %d)\n", values.capacity(), 1 << 20);
}

Twenty-one reallocations for a million pushes. Capacity doubles, so the copies cost 1 + 2 + 4 + … + n < 2n in total — linear across the whole sequence, which is what amortised O(1) means: not “each call is cheap” but “n calls cost O(n)”.

The costs that do not look like loops

This is where solutions time out.

#include <chrono>
#include <cstdio>
#include <set>
#include <vector>

template <class T>
inline void keep(const T& value) { asm volatile("" : : "r,m"(value) : "memory"); }

template <class Body>
double time_it(Body body) {
    auto start = std::chrono::steady_clock::now();
    auto result = body();
    keep(result);
    return std::chrono::duration<double, std::milli>(
        std::chrono::steady_clock::now() - start).count();
}

int main() {
    constexpr int n = 8'000;

    double front = time_it([] {
        std::vector<int> v(n, 1);
        while (!v.empty()) v.erase(v.begin());      // O(n) per call
        return v.size();
    });
    double back = time_it([] {
        std::vector<int> v(n, 1);
        while (!v.empty()) v.pop_back();            // O(1) per call
        return v.size();
    });

    std::vector<int> data(n);
    for (int i = 0; i < n; ++i) data[i] = i;
    std::set<int> lookup(data.begin(), data.end());

    double scan = time_it([&] {
        int hits = 0;
        for (int q = 0; q < n; ++q)
            for (int x : data) if (x == q) { ++hits; break; }   // O(n) per query
        return hits;
    });
    double tree = time_it([&] {
        int hits = 0;
        for (int q = 0; q < n; ++q) hits += static_cast<int>(lookup.count(q));
        return hits;
    });

    std::printf("erase(begin()) x%d : %8.1f ms\n", n, front);
    std::printf("pop_back()     x%d : %8.1f ms\n", n, back);
    std::printf("linear scan    x%d : %8.1f ms\n", n, scan);
    std::printf("set::count     x%d : %8.1f ms\n", n, tree);
}

Erasing from the front is O(n) because everything after it shifts down, so emptying a vector that way is O(n²). Searching a vector for each of n queries is O(n²). Neither loop looks quadratic; the quadratic part is inside a call.

The table to keep in your head:

The last row is a genuine trap: std::lower_bound(s.begin(), s.end(), x) on a std::set compiles, gives the right answer, and is linear. Use s.lower_bound(x), the member function, which is logarithmic.

When the exponent is not the problem

Complexity is about how cost grows, not how large it is. Two consequences that matter in a contest.

Below some size, the worse class wins. Linear search beats a std::set for a few dozen elements: the set allocates a node per element, scatters them across memory, and pays a pointer chase per comparison, while the vector scan is sequential and predictable — Chapter 7.3’s argument. std::sort itself switches to insertion sort for small ranges for exactly this reason.

The constant can be the whole difference. std::map and std::unordered_map are O(log n) and O(1), and in Chapter 9.5’s benchmark the hash map was three times faster on 5,000 string keys — not because log 5000 is 13, but because tree traversal is thirteen dependent pointer chases and a hash is one pass over the string. Meanwhile an unordered_map of integers is frequently beaten by a plain sorted vector with lower_bound, because the vector never allocates and the binary search stays in cache.

The practical rule: use complexity to rule things out, and measurement to choose between what remains. The constraint tells you O(n²) will not fit. It does not tell you which of two linear solutions is faster, and no amount of staring will.

Check yourself

Practice