Step 1 of 6

Big-O in practice

Two programs can give the same answer and still differ enormously: one finishes instantly, the other takes hours. The difference is usually not the language or the computer, but how the amount of work grows as the input gets bigger. Big-O notation describes exactly that growth, ignoring constant factors:

A computer does roughly 10⁸ to 10⁹ simple operations per second. So at a million items, O(n²) takes minutes to hours (a trillion steps) while O(n log n) takes milliseconds. Interviews test this, and so does production traffic.

Counting the work

To find a function's complexity, ask how many times the innermost statement runs for an input of size n:

• One loop over the data: n times, so O(n).
• A loop inside a loop over the same data: about n × n / 2 times, so O(n²). The / 2 is a constant factor, and Big-O drops it.
• A loop that halves the range each time: log₂ n times, so O(log n).

Here the same question, "which numbers appear in both lists?", is answered both ways:

#include <iostream>
#include <unordered_set>
#include <vector>

long ops = 0;

int common_slow(const std::vector<int>& a, const std::vector<int>& b) {
    int n = 0;
    for (int x : a) {
        for (int y : b) {
            ops++;
            if (x == y) { n++; break; }
        }
    }
    return n;
}

int common_fast(const std::vector<int>& a, const std::vector<int>& b) {
    std::unordered_set<int> in_b(b.begin(), b.end());   // O(n) to build
    int n = 0;
    for (int x : a) {
        ops++;
        if (in_b.contains(x)) n++;                      // O(1) average each
    }
    return n;
}

int main() {
    std::vector<int> a, b;
    for (int i = 0; i < 2000; i++) { a.push_back(i * 2); b.push_back(i * 3); }
    ops = 0;
    std::cout << common_slow(a, b) << " common, " << ops << " steps\n";
    ops = 0;
    std::cout << common_fast(a, b) << " common, " << ops << " steps\n";
}

667 common, 3110889 steps
667 common, 2000 steps

With 2,000 numbers the nested loop already does over 3 million steps. With 200,000 it would do tens of billions, while the hash set version would do 200,000.

Trading memory for time

The most common fix for O(n²) is to remember what you've seen in a structure with fast lookup. A hash set uses extra memory, but checks membership in O(1) on average, so one pass over the data is enough.

Your turn: write bool has_duplicate(const std::vector<int>& v) in O(n). The hidden test uses 200,000 numbers, so comparing every pair will run out of time.

Next: Binary search