Big O as you'd say it in an interview

The code runs, and the interviewer asks what it costs. "Linear" gets a follow-up question. "O(n + m) time, where n is the number of items and m the number of coupons, plus O(m) space for the dictionary" usually gets the next problem, because it shows you knew the cost before you finished typing. Getting there takes a handful of habits: knowing which terms to keep, giving each input its own letter, counting costs that arrive in bursts or shrink by halves, reading a recursive function's cost off a drawing of its calls, and saying all of it while you code rather than after.

What the interviewer means by O

Strictly, O gives an upper bound, Ω a lower bound, and Θ both at once, so a single pass over n items is O(n²) on paper as well as O(n). Interviewers use O to mean the tightest bound you can justify, and calling that pass O(n²) gets marked wrong even though it is technically true.

Give two figures: time, and extra space. Space covers every list, set and dictionary you build, and the call stack too. A recursive function that goes d calls deep keeps d frames alive at once, so it uses O(d) space even if it allocates nothing else. Say whether you count the output: "O(1) extra space, not counting the list I return" leaves no room for doubt.

Then pick the case. State the worst case unless you say otherwise. Best case tells the interviewer almost nothing, since nearly any algorithm can check for a lucky input first and stop. Expected case is for algorithms that make random choices or rely on hashing. A Python dict lookup is O(1) on average and O(n) for n keys that all collide; quicksort with a random pivot is O(n log n) expected and O(n²) in the worst case. Calling dict operations O(1) is fine in an interview. Add "on average" once, so the interviewer knows you know about the other case. How hash tables earn that average is covered in Arrays, strings and hash tables.

Constants and smaller terms

O describes how cost grows as the input grows, so constant factors and slower-growing terms drop out. O(3n) is O(n). O(n² + 4n) is O(n²). Two passes over a list and one pass are both O(n).

Drop a term only when another term outgrows it however the inputs vary. O(n + m) stays as it is, because nothing says which list is longer, and O(n² + m) stays too. Also check that a "constant" isn't an input in disguise. A 26-slot array of letter counts is O(1) space when the prompt promises lowercase English letters. If it allows any character, the slot count is the alphabet size, call it a, and the space is O(a).

Constants leave the notation but can come back into the conversation. When two of your answers share a class, a good interviewer may ask which is faster in practice. "Both are O(n); this one reads the data once instead of three times, which matters if it streams from disk" is a real answer about constants. So is choosing a plain O(n²) loop when the prompt caps n at 50 and the clever version is twice as long. Say the reason out loud and it reads as judgment rather than a gap.

Steps in sequence add, steps inside steps multiply

When code does one thing and then another, add the two costs. When it does one thing once per step of another, multiply. Give each input that can vary on its own a separate letter, and say what the letter stands for.

Here a cart of n items meets m coupons, each taking a percentage off one category:

def total_nested(items, coupons):
    total = 0
    for _, category, price in items:              # n items
        best = 0
        for coupon_category, percent in coupons:  # all m coupons, for every item
            if coupon_category == category:
                best = max(best, percent)
        total += price * (100 - best) / 100
    return total                                  # O(n * m) time


def total_with_lookup(items, coupons):
    best_off = {}
    for category, percent in coupons:             # m coupons, once
        best_off[category] = max(best_off.get(category, 0), percent)
    total = 0
    for _, category, price in items:              # n items, once
        total += price * (100 - best_off.get(category, 0)) / 100
    return total                                  # O(n + m) time, O(m) space

In total_nested, the inner loop runs over all m coupons once for every item, so the cost is n × m. total_with_lookup reads each list once and spends O(1) on average per dictionary lookup, for O(n + m) time and O(m) extra space (the dictionary holds at most one entry per coupon). With 2,000 items and 300 coupons, that is 600,000 comparisons against about 2,300 steps.

What the interviewer sees. A candidate calls total_nested "O(n²)". Two inputs have been folded into one letter, and the interviewer has to ask which list n means. The answer changes the verdict: if the store never runs more than three coupons at once, the nested version is linear in the items and perfectly fine. Write n and m down before you start, and keep them apart until the end.

Amortized cost: a rare expensive call

Some operations are cheap on most calls and expensive on a few. Amortized cost is the total cost of a run of n calls divided by n. It is a guarantee about every sequence of calls, not an average over lucky inputs. This writer buffers records and sends them in batches of b:

class BatchWriter:
    """Buffers records and hands them to send() in batches of batch_size."""

    def __init__(self, send, batch_size):
        self.send = send                  # costs O(len(batch))
        self.batch_size = batch_size
        self.buffer = []

    def add(self, record):
        self.buffer.append(record)        # O(1) on most calls
        if len(self.buffer) == self.batch_size:
            self.send(self.buffer)        # O(b) on every b-th call
            self.buffer = []

A single add can cost O(b): the one that fills the buffer pays for sending all of it. But a send happens at most once every b adds and carries exactly the records those adds brought in. Charge each record for its own append and for its own place in one send, and every record pays a constant. So n adds cost O(n) in total, which is O(1) amortized per add, while the worst single call stays O(b).

Give both numbers when they differ, because callers care about different ones. Code that must answer within 5 milliseconds cares about the worst single call; a nightly job cares about the total. Python's list.append follows the same pattern. Once in a while the list outgrows its memory block and may have to copy every element into a bigger one. CPython grows the block by roughly an eighth of its size each time, not by a fixed number of slots, which keeps each element's share of the copying constant, so append is O(1) amortized.

Where log n comes from

A log appears when each step throws away a fixed fraction of what remains. Log base 2 of n, written log₂ n, counts how many times you can halve n before reaching 1. A knockout tournament with 1,024 players takes 10 rounds; a million players take 20. Doubling the field adds one round. That is the signature to listen for: if doubling the input adds a fixed amount of work, the cost is logarithmic.

Balanced trees are the other source. A balanced binary search tree on n keys is about log₂ n levels tall, so walking from the root to a leaf is O(log n). A binary heap is a complete tree, so a push or a pop is O(log n) and reading the smallest item is O(1). The base doesn't matter inside O, since log₂ n and log₁₀ n differ by a constant factor, so just write log n.

Two checks before you say "log". The step must cut the remaining work by a fraction: a loop that subtracts 5 each time (n, n - 5, n - 10 and so on) is linear. And watch what multiplies it: one heap push is O(log n), but pushing n items is O(n log n), the same class as sorting.

Reading a recursive runtime off the call tree

For a recursive function, draw its calls as a tree: one node per call, with a child for each call it makes. The time is the number of nodes times the work each call does outside its recursive calls. The space follows the depth of the tree, because only one path from the top call down to a leaf is on the stack at a time.

This brute-force scheduler tries every way to put n jobs on k machines and returns the smallest possible load on the busiest machine:

def best_finish_time(jobs, k):
    """Try every way to put the jobs on k machines; return the smallest busiest load."""
    loads = [0] * k

    def place(i):
        if i == len(jobs):                # every job placed: a leaf
            return max(loads)             # O(k)
        best = float("inf")
        for m in range(k):                # k children per call
            loads[m] += jobs[i]
            best = min(best, place(i + 1))
            loads[m] -= jobs[i]
        return best

    return place(0)

Each call places one job and tries it on all k machines, so every call that isn't a leaf has k children, and the tree has n levels below the first call. Drawn out for n = 3 jobs on k = 3 machines:

Each level has k times as many calls as the one above, so there are kⁿ leaves. For k ≥ 2 the levels above the leaves add at most as many calls again (here 13 against 27), so there are fewer than 2kⁿ calls in all. Each call does O(k) work of its own: the loop at an inner call, max(loads) at a leaf. That makes the time O(k × kⁿ), and each extra job multiplies it by k. The shape to read off any such drawing is the branching factor raised to the depth, times the work per call.

The space is O(n + k): at most n + 1 frames on the stack at once, plus the loads list. A candidate who counts every call instead of the deepest path will announce exponential space here, and the interviewer sees someone who has mixed up how many calls happen with how many are open at once. When the same subproblem appears at many nodes, remembering its answer cuts the tree down; From recursion to dynamic programming works through that.

Saying it as you code

Say the cost of each piece in a short line as you write it, then add the pieces up when you finish. You'll catch a nested loop the moment you type it, and the interviewer can steer you before you build on it. For the coupon code it sounds like this:

"First I'll build a dictionary from category to best discount. That's one pass over the coupons, so O(m). Now one pass over the items with a lookup each, O(n). So O(n + m) time, and the dictionary is O(m) space."

If you choose the slow version on purpose, say that too: "This is n times m. I'll get it working, then come back to it."

To practice with the questions on this page, write the letters before any code: what n is, what m is, and any other size the prompt gives you. Say the cost of each loop as you write it, and finish with one sentence that gives time and space. Find the Most Frequent Log Call is a quick first drill: its follow-ups bring in a new size, so state the cost again after each one.