Big-O: How Engineers Talk About Speed

Why a cost language exists

You now own containers that make competing speed claims, and the next unit will add more of them, such as map being slower than unordered_map while both beat scanning a vector.

Comparing algorithms needs a measure that does not depend on whose laptop ran the test. A 10-year-old machine and a new one differ by a constant factor, but the shape of an algorithm's cost curve is the same everywhere. Big-O notation is that measure, it is how every interviewer will ask about your solution, and it is how library documentation states its guarantees.

The definition: big-O describes how an algorithm's running time or memory grows as the input size n grows, keeping only the dominant term and ignoring constant factors. Saying an algorithm is O(n) means that doubling the input roughly doubles the work. O(n²) means that doubling the input roughly quadruples it.

The classes you will actually use, each anchored to something you have already written:

O(log n) means halving because a logarithm answers the question of how many times n can be cut in half before reaching 1. For n = 1,000,000 the answer is only about 20, which is why searching a sorted structure by repeated halving crushes scanning element by element.

Counting the halvings of a million

The loop below counts how many times 1,000,000 can be halved before reaching 1, which is the worst case for binary search, and compares it against the worst case for a linear scan.

#include <iostream>

int main() {
    int n = 1000000;
    int steps = 0;
    int remaining = n;
    while (remaining > 1) {
        remaining /= 2;   // each step discards half
        steps++;
    }
    std::cout << "linear scan, worst case: " << n << " steps\n";
    std::cout << "binary search, worst case: " << steps << " steps\n";
    return 0;
}

Output

linear scan, worst case: 1000000 steps
binary search, worst case: 19 steps

The ratio is roughly 53,000 to 1, and that gap is the entire argument for keeping data sorted or indexed. Both algorithms answer the same question, and one of them asks about 19 elements while the other asks about all million.

remaining /= 2 is integer division from lesson 2-2, so the truncation is doing real work here. Halving 25 gives 12 rather than 12.5, which is exactly what binary search does when it discards half of an odd-sized range.

Scaling the input shows why the log column barely moves. Going from a million to a billion, a thousand times more data, takes the linear scan to a billion steps while binary search needs only about 10 more, for 29 total.

Reading big-O off your own code

Three mechanical rules cover most code you will write.

A loop over n items is O(n). A loop inside a loop multiplies, so lesson 3-3's nested pattern with both bounds at n runs its body n × n times, which is O(n²).

Sequential steps add, and the biggest term wins. An O(n) pass followed by an O(n²) pass is O(n + n²), which simplifies to O(n²). For n = 1,000,000 the n² part is a trillion operations while the n part is a millionth of that, so the small term is rounding error, which is exactly why big-O discards it.

Constants are dropped. Looping over the input three times is O(3n), which is O(n). The 3 matters to a profiler, but it does not change the shape of the curve, and the shape is what decides whether your solution finishes at all.

One rule of thumb makes this practical. A judged environment executes very roughly 10⁸ simple operations per second, so for n = 100,000 an O(n²) solution needs about 10¹⁰ operations, which is minutes and an automatic time-limit failure, while O(n log n) needs about 1.7 × 10⁶, which is milliseconds. Estimating this before coding is precisely what interviewers mean when they ask you to discuss complexity first.

The widening gap, in numbers

A loop over three input sizes, printing n beside n², so the two growth rates can be compared directly.

#include <iostream>

int main() {
    for (int n : {10, 100, 1000}) {
        long long squared = 1LL * n * n;   // 1LL forces 64-bit math (lesson 2-1)
        std::cout << "n=" << n << "  n*n=" << squared << "\n";
    }
    return 0;
}

Output

n=10  n*n=100
n=100  n*n=10000
n=1000  n*n=1000000

Each row multiplies n by 10 while n² multiplies by 100. That widening gap is the whole of what big-O is about, and it is why an algorithm's class matters far more than any constant-factor tuning.

Two small techniques are worth naming. The loop iterates over a braced list, {10, 100, 1000}, which is a range-based for from lesson 8-3 over a temporary initializer list rather than over a container. And 1LL * n * n promotes the multiplication to 64-bit before it happens, which is lesson 2-1's overflow rule applied preemptively, since n * n in int arithmetic would overflow for n above about 46,000.

Two sequential passes over the same data

A function that loops over n elements doing a constant-time map lookup, and then separately loops over them again to print, is O(n) overall.

Each loop is O(n) on its own, sequential passes add rather than multiply, and O(2n) drops its constant to become O(n). The lookup was stated to be constant-time, so it contributes no extra factor.

Loops multiply only when one is nested inside the other, and that distinction is the single most common mistake people make when reading complexity off code:

for (int x : v) { use(x); }        // O(n)
for (int x : v) { print(x); }      // O(n), total O(n)

for (int x : v) {                  // O(n) ...
    for (int y : v) {              // ... times O(n)
        compare(x, y);             // total O(n squared)
    }
}

The nested version of the same idea, scanning the whole vector for each element, would be O(n²). Replacing that inner scan with a constant-time hash lookup is how a great many O(n²) solutions become O(n), and unit 9's unordered_map is the tool for it.