How to explain Big O out loud in an interview

Where I come from, we read how pressure grows as the water gets deeper. Big O asks the same question about code. How does the work grow as the input grows?

Expect the question once your code runs. What is the time and space complexity? A bare label sounds memorized. A short reason sounds like thinking. This is the script I use to give the reason.

Say the reason, then the label

Walk the code in the order it runs. Count how often the work repeats. Then give the label.

1. Name the input. "Let n be the length of the array."
2. Find the repeated work. "I visit each element once."
3. Give the cost, then the label. "Each visit is constant work, so the time is O(n)."
4. Say the space, including what you store. "I keep a set of up to n items, so the space is O(n)."

Two rules keep the numbers honest. Drop constants: two passes over n items is still O(n). Keep only the fastest-growing term: n squared plus n is O(n squared). Space counts what you add, not the input you were given. Interview Cake walks through all three rules with more examples.

Three examples, said out loud

The first example has one loop.

def largest(items):
    best = items[0]
    for item in items:
        if item > best:
            best = item
    return best

One pass, with constant work per item. That is O(n) time. I keep two variables whatever the input size, so the space is O(1).

The second example compares every item with every item after it.

def has_repeat(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

For each item, I scan the ones after it. That makes about n squared over two comparisons. Drop the constant and I get O(n squared) time and O(1) space.

Now watch the trade. Here is the same function with a set.

def has_repeat(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

Here is how I would say it:

n is the length of the list. I make one pass and do constant work per item, so the time is O(n). The set holds up to n items, so the space is O(n). I traded space for time.

A set lookup is constant time on average. The worst case is slower. If the interviewer asks, I say that too.

The third example needs no code. Binary search throws away half the range at every step. A thousand items take about ten steps, because two to the tenth is 1,024. That is O(log n).

The costs that hide

Counting loops is half the job. The calls inside a loop have costs too.

• Sorting first costs O(n log n). Say it when you sort, even if the rest is linear.
• In Python, x in items and items.pop(0) both walk the list. Each is O(n), so inside a loop they turn it into n squared.
• A slice copies. A slice inside a loop is a hidden second loop.
• Recursion uses space. The call stack grows with the depth, so a tree walk uses O(h) stack, where h is the height.
• Two inputs need two letters. Comparing an array of n with one of m is O(n + m), not O(n).

The Python wiki lists the cost of each built-in operation. Read it once, and you will stop guessing.

Average, worst and amortized

Name which case you mean. Set lookups are constant on average and linear in the worst case. Appending to a Python list is O(1) amortized.

Amortized means most appends are cheap and an occasional resize costs more. Spread over many appends, the cost evens out. Say "amortized" when you mean it, and say what it covers.

When the interviewer pushes back

Sooner or later you will hear, "Can you do better?" Don't panic and don't guess. Find the bottleneck first.

In the nested version, the bottleneck is the inner scan. It re-reads the same items for every outer item. I ask what I could remember from the first pass so I never scan again. That question leads to the set.

Say the bottleneck out loud before you change any code. The sentence shows you understand why the code is slow. The faster version rests on that understanding.

Practice it where it counts

Do this after every problem. Before you look anything up, say the four steps out loud. Then check yourself against the code. The step that feels shaky is the one to rehearse.

Coco is the AI study partner on StrongYes. She is not a person. She listens while you explain your code and asks one question at a time. She never hands you the fix.

The editor and the code runner are free. Open the editor, solve something small, and say your complexity before you press Run. Contains Duplicate and Binary Search make good first tries.

Pair this with the questions to ask before you write any code.