Big-O and measuring

Big-O is a way to say how the work grows as the input grows, ignoring constant factors. It's the first filter for whether an approach can possibly work ("10⁶ elements, O(n²): no"). Measurement is the second: two O(n log n) programs can differ tenfold, and a cache miss can cost more than a hundred additions. You need both, and you need to measure honestly.

1. What the notation says — and doesn't

For a cost function f(n):

So 3n² + 5n + 100 is Θ(n²): the lower-order terms and the constant 3 don't change the growth. It's also O(n³) — true but useless, which is why people usually say O when they mean Θ. When it matters ("this algorithm is optimal"), be precise.

A separate question is which case you're bounding:

• worst case — the most work over all inputs of size n (std::unordered_map::find is Θ(n) worst case: every key in one bucket);
• average case — expected work under some input distribution (the same find is O(1) on average with a good hash);
• amortized — average per operation over a sequence of operations, with no probability involved (vector::push_back is amortized O(1); one call may copy everything, but n calls copy at most ~2n elements in total).

"O(1) average" and "O(1) amortized" are different promises. Know which one you're relying on.

2. Counting work in loops

Count how many times the innermost statement runs, as a function of n.

#include <print>

int main() {
    const int n = 1000;
    long long a = 0, b = 0, c = 0, d = 0;

    for (int i = 0; i < n; ++i)              // n
        for (int j = 0; j < n; ++j) ++a;     //   × n          = n²

    for (int i = 0; i < n; ++i)              // inner runs i times:
        for (int j = 0; j < i; ++j) ++b;     // 0 + 1 + … + (n-1) = n(n-1)/2  → still Θ(n²)

    for (int i = n; i > 0; i /= 2) ++c;      // halving: ⌊log₂ n⌋ + 1 iterations → Θ(log n)

    for (int i = 1; i <= n; ++i)             // inner runs n/i times:
        for (int j = i; j <= n; j += i) ++d; // n(1 + 1/2 + … + 1/n) ≈ n ln n → Θ(n log n)

    std::println("n²={} triangle={} halving={} harmonic={}", a, b, c, d);
}

Three patterns cover most code:

• Dependent bounds (j < i): the sum 0 + 1 + … + (n−1) = n(n−1)/2. Halving the work doesn't change the class — it's still Θ(n²).
• Halving / doubling (i /= 2, i *= 2): log₂ n steps. Binary search, balanced trees, and "how many times can I halve this" all live here.
• Geometric sums: if each round does half the work of the previous one, the total is at most twice the first round. for (i = n; i > 0; i /= 2) with an inner loop of i steps does n + n/2 + n/4 + … < 2n work — Θ(n), not Θ(n log n).

And the harmonic sum 1 + 1/2 + … + 1/n ≈ ln n shows up whenever the inner loop strides by the outer index (sieve of Eratosthenes, "for each divisor").

3. What fits in a second

A modern core does roughly 10⁸–10⁹ simple operations per second, depending on how cache-friendly they are. That gives a budget:

Read it backwards when you see input limits: n ≤ 10⁵ means O(n²) (10¹⁰ operations) is out and you need O(n log n) or better; n ≤ 20 hints that exponential search over subsets is intended.

4. Costs of standard operations

Many slow programs are a fast-looking call inside a loop.

The classic accident: while (!v.empty()) { use(v.front()); v.erase(v.begin()); } looks linear and is Θ(n²). Iterate instead, or erase from the back, or use a std::deque.

5. Constants and caches matter

Big-O hides constant factors, and memory layout is the biggest one. Summing a std::vector<int> streams through contiguous memory that the prefetcher loves; summing a std::list<int> of the same size chases a pointer to a possibly cold cache line per element. Both are Θ(n). The list is commonly 5–50× slower. When two approaches have the same complexity, measure.

6. Measuring honestly

A timing you can trust needs:

1. An optimised build (-O2). Debug or sanitizer builds measure something else.
2. A monotonic clock: std::chrono::steady_clock (system_clock can jump).
3. Repetition: run several times and keep the minimum (or the median). Noise from other processes only ever adds time, so the minimum is the most repeatable estimate.
4. A result the compiler can't delete: if the result is never used, the optimiser may remove the work entirely. Feed it to an opaque sink.
5. Several sizes, not one. One number tells you nothing about growth.

Then fit the growth exponent: if time ≈ c·nᵏ, then log(time) = log c + k·log n, a straight line in log-log space whose slope is k. A slope near 1 means linear (n log n reads as ~1.1), near 2 means quadratic. This is exactly how this app's complexity probe grades your builds.

#include <algorithm>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <print>
#include <vector>

// An opaque use of v: the compiler must assume the asm reads it.
template <class T>
void do_not_optimize(const T& v) {
    asm volatile("" : : "r,m"(v) : "memory");
}

template <class F>
long long best_ns(F&& f, int repeats = 5) {
    long long best = -1;
    for (int r = 0; r < repeats; ++r) {
        auto t0 = std::chrono::steady_clock::now();
        f();
        auto t1 = std::chrono::steady_clock::now();
        long long ns = std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count();
        if (best < 0 || ns < best) best = ns;
    }
    return best;
}

int main() {
    std::vector<double> xs, ys;
    for (std::size_t n : {1u << 12, 1u << 13, 1u << 14, 1u << 15}) {
        std::vector<std::int64_t> v(n, 1);
        long long ns = best_ns([&] {
            std::int64_t s = 0;
            for (auto x : v) s += x;
            do_not_optimize(s);
        });
        xs.push_back(std::log(static_cast<double>(n)));
        ys.push_back(std::log(static_cast<double>(std::max(ns, 1LL))));
    }
    // Least-squares slope of log(time) against log(n).
    double mx = 0, my = 0;
    for (std::size_t i = 0; i < xs.size(); ++i) { mx += xs[i]; my += ys[i]; }
    mx /= xs.size(); my /= ys.size();
    double num = 0, den = 0;
    for (std::size_t i = 0; i < xs.size(); ++i) {
        num += (xs[i] - mx) * (ys[i] - my);
        den += (xs[i] - mx) * (xs[i] - mx);
    }
    std::println("slope ≈ {:.2f} (expect about 1 for a linear scan)", num / den);
}

(Run here, the slope is rough: tiny inputs, an instrumented build, a shared machine. That's the point of the list above — the probe uses -O2, bigger sizes, and compares against a reference measured the same way.)

7. Worked example: "is there a duplicate?"

The direct approach compares every pair:

for (std::size_t i = 0; i < v.size(); ++i)
    for (std::size_t j = i + 1; j < v.size(); ++j)
        if (v[i] == v[j]) return true;   // n(n-1)/2 comparisons: Θ(n²)
return false;

The repeated work: every element is compared against everything again. If we sort first, equal values become neighbours, and one pass suffices: Θ(n log n) for the sort plus Θ(n) for the scan. A hash set gives Θ(n) on average — insert each value; if it was already there, it's a duplicate.

#include <algorithm>
#include <print>
#include <span>
#include <unordered_set>
#include <vector>

bool has_duplicate_sort(std::span<const int> v) {
    std::vector<int> s(v.begin(), v.end());   // copy: the input is read-only
    std::ranges::sort(s);
    return std::ranges::adjacent_find(s) != s.end();
}

bool has_duplicate_hash(std::span<const int> v) {
    std::unordered_set<int> seen;
    seen.reserve(v.size());
    for (int x : v)
        if (!seen.insert(x).second) return true;   // insert reports "already there"
    return false;
}

int main() {
    std::vector<int> v{4, 8, 15, 16, 23, 42, 15};
    std::println("{} {}", has_duplicate_sort(v), has_duplicate_hash(v));
}

Which is faster in practice? For ints, sorting is often competitive: it's cache-friendly and allocates once, while the hash set allocates nodes and hashes every value. Big-O narrows the field; measurement picks the winner.

Faded example — your turn

Count the pairs i < j with v[i] + v[j] == target. The brute force is the same double loop. Following the hash-set idea, what should you remember about the elements you've already passed — and why is a set not enough?

std::unordered_map<long long, long long> seen;   // value -> ???
long long pairs = 0;
for (int x : v) {
    pairs += /* ??? */;
    /* ??? */;
}

Summary

• O is an upper bound, Ω a lower bound, Θ both. Worst / average / amortized are a separate axis.
• Count innermost iterations: dependent bounds stay Θ(n²), halving gives log n, geometric sums collapse to the first term, strides by i give n log n.
• Budget ~10⁸ simple operations per second; read input limits backwards.
• Know the cost of each library call you put inside a loop.
• Measure with -O2, steady_clock, repeats (keep the minimum), an opaque sink, and several sizes; the log-log slope estimates the exponent.