Big-O on autopilot

Big-O is a shorthand for how fast the amount of work grows as the input gets bigger. It is NOT a stopwatch — it does not tell you "this takes 4 milliseconds." It answers a different question: if your input suddenly got 10 times larger, would the work stay the same, grow 10 times, grow 100 times, or blow up completely? We write it as O(...): O(1) means flat (the work never changes), O(n) means it grows in step with the input, and O(n²) means it grows like the input squared. The "n" is just the size of the input — the number of items in your list, say.

Because we only care about that growth shape at large sizes, we throw away two kinds of clutter. We drop constants (a "times 3" or "times 100" out front), and we drop lower-order terms (smaller pieces added on). So 3n + 50 simplifies to just O(n): when n is huge the "+50" is a rounding error, and the "times 3" doesn't change the fact that it's still a straight line. Only the fastest-growing piece survives.

Turning a chunk of code into a Big-O is mostly two rules. Steps done one after another ADD, and you keep the biggest — a loop followed by a separate loop is O(n) + O(n), which is still just O(n). Steps nested inside each other MULTIPLY — a loop running inside another loop, both over the same n items, is O(n) × O(n) = O(n²). A "loop" here just means repeating a block of work once per item.

Picture a classroom. If the teacher walks the row and high-fives each student, that's one pass — O(n), and doubling the class doubles the high-fives. But if every one of the n students greets every student (a loop inside a loop), each does about n greetings, so the total is about n × n. Double the class and the greetings roughly quadruple. That explosion is the O(n²) "compare every pair" pattern — most clever algorithms exist to dodge it. Here it is traced on a tiny list of 3 numbers, [3, 5, 9]: the outer loop picks one item (highlighted), and the inner loop walks every item to pair against it.

Why does this matter so much? Because the growth shape decides whether your solution finishes at all. The lesson's constraint decoder turns this into a hint: if a problem says n can be up to 10⁶ (a million), an O(n²) solution would need a trillion steps and never finish — so the size of n is quietly telling you which Big-O you're allowed to aim for. Reading "n ≤ 10⁶" as "I need O(n) or O(n log n)" is the reflex this whole lesson is training.

Before you can pick the right algorithm, you need a shared language for how the work grows as the input grows. That's all Big-O is — and once it's reflexive, every later phase gets cheaper.

Every term, defined once

The walkthrough above gave you the feel; this section pins down each word so nothing is left fuzzy. Read it once and the rest of the lesson is just vocabulary you already own.

• Big-O — a notation for the upper bound on how the work (or memory) of an algorithm grows as the input size n grows. "O" stands for "order of." It deliberately ignores hardware, language, and exact step counts; it captures only the shape of the growth curve at large n.
• n — the size of the input. Usually the number of items (length of a list, number of nodes in a graph, characters in a string). If there are two independent sizes, we name them separately, e.g. m and n.
• Time complexity — how the number of operations grows with n. This is what people mean by default when they say "the Big-O."
• Space complexity — how the extra memory grows with n. "Extra" means memory you allocate beyond the input itself: new arrays, hash maps, and — easy to forget — the recursion call stack (see the space note below).
• Best / worst / average case — the same algorithm can do different amounts of work depending on the specific input. Best case is the luckiest input, worst case is the most punishing, average case is what you expect over typical inputs. Interviews almost always mean worst case unless they say otherwise, because that's the guarantee you can actually promise. Example: linear search for a value is O(1) best case (it's the first element) but O(n) worst case (it's last or absent), so we call it O(n).
• Amortized — the average cost per operation across a long sequence, even when one occasional operation is expensive. Appending to a dynamic array (Python list.append) is O(1) amortized: almost every append is cheap, and the rare "the array is full, copy everything to a bigger buffer" step (which is O(n)) is so infrequent that, spread over all the appends, the average stays O(1). Amortized is a promise about the long run, not about any single call.

With that lens, here's the ladder to recognize on sight — and the solution shapes that land on each rung:

Each class, in one line of plain English

The table above is the cheat sheet; here is what each rung actually means, plus a rough cap on how big n can be before that complexity stops finishing in about one second (assume a machine does very roughly 10⁸–10⁹ simple operations per second — a useful back-of-envelope, not a guarantee):

Counting loops: traced snippets

You already have the two rules — sequential adds, nested multiplies. Here they are applied to real code so the counting becomes mechanical. The trick is to ask, for each loop, "how many times does this run, as a function of n?" then combine.

# SEQUENTIAL — two separate loops, one after the other.
for x in items:        # runs n times
    print(x)
for y in items:        # runs n times (separate sweep)
    print(y)
# total = n + n = 2n  -> drop the constant  -> O(n)

# NESTED — a loop inside a loop, both over the same n items.
for x in items:        # outer runs n times
    for y in items:    # inner runs n times FOR EACH outer step
        print(x, y)
# total = n * n = n^2  -> O(n^2)

# TRIANGULAR — inner loop starts at i, so it shrinks each pass.
for i in range(n):     # outer runs n times
    for j in range(i, n):  # inner runs (n-i) times
        work(i, j)
# total = n + (n-1) + ... + 1 = n(n+1)/2 ~ n^2/2  -> still O(n^2)
# LESSON: half of a square is still a square. Drop the 1/2.

# HALVING — the counter multiplies, so the loop count is logarithmic.
i = 1
while i < n:           # i doubles: 1, 2, 4, 8, ... up to n
    work(i)
    i = i * 2           # it takes ~log2(n) doublings to reach n
# total ~ log2(n) iterations  -> O(log n)

# SORT THEN SCAN — sequential, so add and keep the biggest term.
items.sort()           # O(n log n)
for x in items:        # O(n)
    work(x)
# total = O(n log n) + O(n)  -> O(n log n)  (n log n grows faster)

Space complexity: the call stack counts

Time is only half the story; interviewers also ask about extra memory. The rule mirrors time: count the size of any data you allocate as a function of n. Building a new list of all n items is O(n) space; using a handful of fixed variables is O(1) space ("in place").

The piece people forget: recursion is not free in space. Every pending recursive call sits on the call stack — a stack of paused function frames waiting for the deeper calls to return — and each frame uses memory. So the space cost of a recursive function is at least the maximum depth it reaches, even if it allocates no arrays at all.

# Counts down to 0. Each call waits for the next, so n frames
# are stacked at the deepest point.
def countdown(n):
    if n == 0:
        return
    countdown(n - 1)   # one deeper call each time
# TIME:  O(n)  — n calls total
# SPACE: O(n)  — stack depth reaches n before any call returns

Compare that to a loop doing the same job: for i in range(n): ... is O(n) time but O(1) space — no frames pile up. And a recursion that halves its input each call, like binary search, only reaches depth log n, so it's O(log n) space. The shape of the recursion's depth, not its total number of calls, sets the stack space.

The constraint decoder, reversed

The most useful trick in a timed setting runs the table backwards: the problem hands you the maximum n, and that number quietly tells you which complexity you're allowed to aim for. If your first idea is too slow for the given n, the constraint is a hint to find a better one.