Time & Space Complexity

In this lesson:

• what Big-O actually measures, and what it deliberately ignores
• the complexity classes you'll name in every interview
• space complexity, including the recursion stack
• the embedded caveats: constants matter, and worst-case (WCET) is king
• the space-time tradeoff that drives lookup tables and hashing

Why two correct programs aren't equal

Searching a sorted 10,000-entry calibration table two ways:

linear scan:   up to 10,000 comparisons
binary search: up to 14 comparisons   (log2(10000) ≈ 13.3)

Both find the value. One scales; one doesn't. Big-O notation captures that difference: how does cost grow as the input size n grows?

What Big-O measures

Big-O describes the growth rate of an algorithm's cost as a function of input size n, keeping only the dominant term and dropping constant factors. It's an upper bound, usually the worst case.

• Drop constants: 3n + 100 → O(n).
• Keep the dominant term: n² + 5n + 9 → O(n²).
• It answers "how does it scale," not "how many milliseconds."

O(n²+5n) and O(n²) are the same class: for large n the n² term dominates.

The classes you must know

ops
 │            O(2^n)   O(n^2)
 │              ╱        ╱
 │             ╱      ╱        O(n log n)
 │            ╱    ╱        ╱
 │          ╱  ╱      ╱        ____ O(n)
 │        ╱╱     ╱___╱______________ O(log n)
 │      ╱╱__╱___╱──────────────────── O(1)
 └──────────────────────────────────── n

A practical sniff test: a single loop over the input is O(n); a loop inside a loop over the same input is O(n²); halving the search space each step is O(log n).

// O(n) — one pass
for (size_t i = 0; i < n; i++) sum += a[i];
 
// O(n^2) — every pair
for (size_t i = 0; i < n; i++)
    for (size_t j = 0; j < n; j++)
        if (a[i] == a[j] && i != j) dup = true;

Space complexity

The same idea applied to memory: how does extra memory grow with n? In-place algorithms are O(1) extra space; one that allocates a copy is O(n).

Don't forget the call stack: recursion costs O(depth) stack space. Recursing n deep is O(n) space even if you allocate nothing, and on an MCU with a few KB of stack, that's a real overflow risk (recall the stack lesson).

// O(1) extra space — reverses in place
void reverse(int *a, size_t n) { /* two-pointer swap */ }
 
// O(n) space — recursion n deep uses n stack frames
int sum_rec(const int *a, size_t n) {
    return n == 0 ? 0 : a[0] + sum_rec(a + 1, n - 1);   // n frames!
}

The embedded caveats Big-O hides

Big-O is essential but it drops exactly the things firmware sometimes cares about most:

Constants matter at small n. Big-O is about large n. On an MCU, n is often tiny (8 sensors, 16 queue slots). An O(n²) insertion sort can beat an O(n log n) quicksort for n=10 because the constant factors and code size are smaller. Measure; don't assume the asymptotically-better algorithm wins at your n.

Worst case is the one that matters (WCET). Hard-real-time code is bounded by its worst-case execution time, not its average. A hash table is O(1) average but O(n) worst (all keys collide), that worst case may be unacceptable in an ISR, where a deterministic O(log n) or a bounded structure is safer.

Memory is a hard ceiling. An O(1)-time hash lookup that needs a 64 KB table doesn't fit a part with 8 KB of RAM. The space term isn't a footnote on embedded, it can be the deciding constraint.

The space-time tradeoff

You can often spend memory to save time, or vice versa. This is the engine behind two later lessons:

• Lookup tables: precompute results into a table → turn an O(n) or expensive runtime computation into an O(1) read (costs flash/RAM for the table).
• Hashing: spend memory on a sparse table → turn O(n) search into O(1) average lookup.

The art on embedded is choosing where you sit on that curve given your flash, RAM, and timing budget.

Gotchas

• Dropping constants can mislead at small n. O(n log n) "beats" O(n²) only once n is large enough. For the tiny n common in firmware, benchmark, the simpler O(n²) may win on speed and code size.
• Average ≠ worst case. Quote both. Hash lookup and quicksort are great on average but have bad O(n)/O(n²) worst cases that matter for WCET.
• Recursion has hidden space cost. O(depth) stack frames. Deep or unbounded recursion overflows a small stack; prefer iteration when depth scales with input.
• Big-O ignores memory hierarchy. Two O(n) loops can differ 10× from cache/prefetch effects (next lesson). Asymptotics don't capture locality.

TL;DR

• Big-O describes how an algorithm's cost grows with input size n, dropping constants and lower-order terms; it's usually a worst-case upper bound.
• Memorize the ladder: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ); one loop is O(n), nested loops O(n²), halving is O(log n).
• Space complexity counts extra memory, including O(depth) recursion stack, a real overflow risk on small MCUs.
• On embedded, mind what Big-O hides: constants (the simpler algorithm often wins at small n), worst case / WCET (average-case O(1) isn't enough for hard real time), and absolute memory (a big table may not fit).
• The space-time tradeoff, spend memory to save time, underlies lookup tables and hashing.