Shelf · DSA Patterns · Chapter 2

Chapter 2: Complexity fluency

Complexity is a count of work you can derive, not a label you recall. This chapter gives you the cost models, the habit of counting hidden Python work, and the judgement to say when a quadratic loop is the right answer.

Difficulty
Priority
dsa-02-01Card 1 of 6

Complexity and amortization

MediumP1 · Must knowKnow cold7 min
complexityamortizedbig-odynamic-array
Needs: nothing. Start here.

Why you care

Most "it was fast in testing" incidents in ETL are cost-model mistakes: a job that was instant on 40,000 rows crawls on 400,000 because one linear line sat inside a loop. On the job you must say which claim a number makes: worst case, expected, or amortized. Interviewers ask about amortization because it separates a per-call guarantee from a per-run one.

Explain like I'm 5

A bus conductor collects fares. Most stops cost a nod. Occasionally the bus is full and everyone changes to a bigger bus, and that stop is slow. The cost per stop over the route is small, because bigger buses are bought rarely. That average is the amortized cost, not a promise about one stop.

Core concept

Three questions hide behind "complexity":

  • Worst case: maximum work over all inputs of size n; holds for every call.
  • Expected case: average over a stated input distribution or the algorithm's random choices. Hash lookup is O(1) on average if keys spread out; the CPython docs say that if every key hashes to the same value each operation takes O(n). That is average-case, not amortization.
  • Amortized case: the worst-case total of m operations divided by m. No probability, any sequence, silent about one call.

Big-O is an upper bound (n steps is also O(n²)); Theta is the tight bound. Mean Theta when you quote a cost.

Prove amortized bounds by aggregate counting, which means totalling the work: with doubling, copies happen at sizes 1, 2, 4, and so on, so n appends copy under 2n items. Or by charging: each item pays a fixed fee when pushed that covers its one later move or pop.

Decision rule: use worst case when one call has a deadline, expected when you can defend the input distribution, amortized when only the run total matters.

Minimal example Counting copies in a doubling array

PythonTotal copies stay under 2nruns
cap, size, copies = 1, 0, 0
for _ in range(1000):
    if size == cap:
        copies += size
        cap *= 2
    size += 1
print(size, cap, copies)
print(copies < 2 * size, copies / size)
Output
1000 1024 1023
True 1.023

In production Each pushed item is popped at most once

A nested while looks quadratic. Charging shows it is not: each reading is pushed once and popped at most once. The block prints the worst single step and the total.

PythonWorst step is linear, total work is notruns
def track(readings):
    stack, pushes, pops, worst_step = [], 0, 0, 0
    for r in readings:
        step = 0
        while stack and stack[-1] <= r:
            stack.pop()
            pops += 1
            step += 1
        stack.append(r)
        pushes += 1
        worst_step = max(worst_step, step)
    return stack, pushes, pops, worst_step


readings = [9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 3, 2, 12]
stack, pushes, pops, worst = track(readings)
n = len(readings)
print("n", n, "pushes", pushes, "pops", pops)
print("worst single step", worst, "of", n)
print("pops <= pushes:", pops <= pushes)
print("left on stack", stack)

for size in (1_000, 10_000):
    data = list(range(size, 0, -1)) + [size + 1]
    _, pu, po, wo = track(data)
    print(size, "worst step", wo, "total pops", po, "pops/n", round(po / len(data), 3))
Output
n 13 pushes 13 pops 12
worst single step 9 of 13
pops <= pushes: True
left on stack [12]
1000 worst step 1000 total pops 1000 pops/n 0.999
10000 worst step 10000 total pops 10000 pops/n 1.0

See it happen A full array pays once, then goes quiet

array, capacity 4replacement, capacity 8abcdefgh
  1. Three appends fill slots 0 to 2 and each costs one write.
  2. The fourth append fills the last slot; the array is exactly full.
  3. The fifth append finds no room, so a larger array is allocated and nothing is copied yet.
  4. All four existing items are copied across: this one append costs about n.
  5. The new item is written and the old array is released.
  6. Three more appends cost one write each, which pays for the earlier copy.
Notice: the expensive append is real and lands when you cannot choose, but the cheap ones after it are what the bound averages over.
Scenario A

In your world

The situation

Your reconciliation job drains unmatched settlement ids with queue.pop(0) in a Jenkins stage with a 30-minute timeout. At 40,000 ids it takes seconds.

What actually breaks

At 400,000 ids the stage slows about 100× and eventually misses its window, and your code raised nothing. Each pop(0) shifts every remaining element: about n²/2 moves, 8×10¹⁰ versus 8×10⁸.

What you'd do on Monday

Use a structure with O(1) front removal. The amortized claim for end append and pop() does not cover pop(0).

PythonFront removal without shifting
from collections import deque

pending = deque(unmatched_ids)      # O(n) once
while pending:
    sid = pending.popleft()         # O(1), no shifting
    reconcile(sid)
Scenario B

Imagine you work at Netflix

50k events/s into a per-consumer buffer

The numbers

Illustrative: a consumer appends 50,000 playback events/s to a list flushed each minute: 50,000 × 60 = 3,000,000 appends, a 24 MB array at 8 B per slot. At growth factor 1.125, total copying is about n/(g-1) = 3,000,000 / 0.125 = 24,000,000 moves, 8 per append. The last resize alone moves about 2.6M slots, roughly 21 MB, in one call.

What the Scenario-A answer does here

The Scenario A fix still holds, but "append is O(1)" is not a latency budget. One append copies 21 MB and stalls the consumer while events keep arriving.

What flips at this scale

The question changes from the average to the worst single call. The consumer uses a fixed-capacity buffer (deque(maxlen=...) or a pre-sized list) flushed on count or time, so no hot-path call is linear.

The trade-off you'd defend

I would defend a fixed-capacity buffer over an unbounded list, trading simplicity and unbounded growth for a bounded worst-case call and a memory ceiling I can alert on.

Illustrative figures chosen to make the arithmetic visible; not Netflix-published numbers.

Gotchas

Amortized append quoted as a latency bound

Symptom

p99 of a handler that appends to a growing list spikes periodically while the mean is flat.

Cause

append is O(1) amortized; the call that triggers a resize copies the whole list.

Fix

Preallocate, cap the buffer, or flush at a fixed size.

Hash average mistaken for a guarantee

Symptom

A service keyed on user-supplied strings crawls on a crafted batch.

Cause

O(1) lookup assumes keys spread out; heavy collisions make each operation O(n).

Fix

State the assumption; cap input size.

Tricky questions

Is "O(n) amortized" the same as "O(n) on average"?
Most people say

Yes, both mean usually fast and occasionally slow.

Actually

No. Average needs a probability assumption about inputs. Amortized is a worst-case total over any sequence divided by its length.

Scenario question

A teammate says "append is O(1), so latency is fine", but p99 spikes every few seconds. How do you respond?

Model answer

I'd say they are quoting an amortized bound as a worst-case one, and I'd confirm by logging list length on slow calls. If the spike matters, I'd use a fixed-capacity buffer flushed by size, accepting a drop-or-block policy when it fills. The trade-off is simplicity against a bounded worst-case call.

Interview corner

CommonWhat is amortized analysis?
“I'd say it is the total cost of any sequence of m operations divided by m. Rare linear copies in a dynamic array are paid for by many cheap appends, but one call can still be linear.”
TrickIs hash-table lookup O(1) amortized?
“I'd say no. It is O(1) on average if keys spread out and O(n) worst case if everything collides. I'd name the assumption before quoting the number.”
CommonWhat is the difference between Big-O and Theta?
“I'd say Big-O is an upper bound and Theta is tight. Calling a linear scan O(n²) is true but useless, so I mean Theta unless I say otherwise.”

Memory hook

A bus conductor's average fare time is tiny, but the stop where everyone changes buses takes as long as the whole bus.

If you remember only one thing:

Amortized is a promise about the total over a run, never about one call.

Self-check

  1. What separates amortized from average-case cost?

    Amortized is a worst-case total over any sequence divided by its length; average-case needs a probability assumption.

  2. Why is doubling-array append O(1) amortized?

    Copies happen at sizes 1, 2, 4, and so on, so n appends copy under 2n items.

  3. Why is a while inside a for not automatically O(n²)?

    If each item is pushed and popped at most once, inner runs total at most n.

Prove it

Extend the doubling simulation to track the largest single-append copy. Run n = 1,000, 100,000 and 1,000,000 and paste three lines of n, total copies, copies/n, largest copy. Success means copies/n stays under 2 while the largest copy grows with n.

dsa-02-02Card 2 of 6

Derive cost from work rather than indentation

MediumP1 · Must knowKnow cold7 min
complexityloopscountinghidden-cost

Why you care

Code that "looks linear" is the usual culprit when a job slows faster than its data grows. One x in some_list or items[i:] inside a loop makes it quadratic, and neither line looks expensive. Interviewers ask for the complexity right after you write something clean. This card teaches counting work: how many times each unit of work can run in total, including work hidden inside built-ins.

Explain like I'm 5

Count how many times a postman walks to a door, not how many streets he walks along. A hundred doors is 100 visits; if he must also check a 100-name list at each, that is 100 × 100 checks.

Core concept

For each line ask how often it runs and what one run costs, then add.

  • Sequential phases add. A sort (n log n) then a scan (n) is O(n log n); the dominant term wins.
  • Nested loops multiply only if bounds are independent. for j in range(i) inside for i in range(n) runs n(n-1)/2 times: Theta(n²).
  • Different inputs get different names. n orders against m rules is O(n·m); writing both as n hides the faster-growing factor.
  • Monotone pointers are charged by movement. If two indices only move forward and are bounded by n, the loop does at most 2n moves however it is nested.
  • Hidden work counts. x in list is O(n). items[i:j] copies j-i elements. insert(0, x), pop(0), sorted and list concatenation cost a size. A sort does about n log n comparisons, each costing whatever the key or __lt__ costs, so n strings of length L cost up to L · n log n character work.

Decision rule: write the cost beside each statement, multiply along nesting only when counts are independent, and look up any built-in before trusting the loop count.

Minimal example Triangular work from a slice in a loop

PythonSlices copy, so the loop is quadraticruns
a = list(range(1000))
n = len(a)
copied = sum(len(a[i:]) for i in range(n))
print(copied, n * (n + 1) // 2)
print(copied > 100 * n)
Output
500500 500500
True

In production Counting comparisons, not guessing

A key class counts how often == runs. The list version compares each new key with everything seen; the set version hashes first, so equality runs only on a hash match.

PythonDedupe: list membership versus set membershipruns
class Key:
    eq_calls = 0

    def __init__(self, v):
        self.v = v

    def __hash__(self):
        return hash(self.v)

    def __eq__(self, other):
        Key.eq_calls += 1
        return self.v == other.v


def dedupe_list(keys):
    seen, out = [], []
    for k in keys:
        if k not in seen:
            seen.append(k)
            out.append(k)
    return out


def dedupe_set(keys):
    seen, out = set(), []
    for k in keys:
        if k not in seen:
            seen.add(k)
            out.append(k)
    return out


n = 400
for fn in (dedupe_list, dedupe_set):
    Key.eq_calls = 0
    out = fn([Key(i) for i in range(n)])
    print(fn.__name__, len(out), Key.eq_calls)
print("triangular n(n-1)/2 =", n * (n - 1) // 2)
Output
dedupe_list 400 79800
dedupe_set 400 0
triangular n(n-1)/2 = 79800
Scenario A

In your world

The situation

Your S3-to-Postgres job skips rows whose txn_id is already loaded, via if txn_id in loaded_ids where loaded_ids is a list from yesterday's audit table. There are 48,213 new rows and 48,000 loaded ids. Review said "single loop, linear".

What actually breaks

Worst case is 48,213 × 48,000 ≈ 2.3×10⁹ comparisons. It passes today. When the audit table doubles, the work doubles to 4.6×10⁹ and the margin to the Jenkins window shrinks; the first signal may be a red build at 02:00.

What you'd do on Monday

Name the sizes separately (rows n, audit size m), see that the line is O(m) inside an O(n) loop, and swap the container.

PythonBuild the lookup once
loaded = set(audit_ids)                                   # O(m) once
fresh = [r for r in rows if r["txn_id"] not in loaded]    # O(n) lookups
Scenario B

Imagine you work at Flipkart

5M price updates per second against a 200k watchlist

The numbers

Illustrative: 5,000,000 price-change events per second are checked against a 200,000-SKU watchlist. With a list the worst case is 5,000,000 × 200,000 = 10¹² comparisons per second. A set costs 200,000 hashes once, then 5,000,000 lookups per second. If one Python process sustains about 1,000,000 lookups/s (an assumption), you need at least 5 processes.

What the Scenario-A answer does here

The Scenario A fix (hash the smaller side once) still answers lookup cost. What breaks is assuming one process: at the assumed 1,000,000 lookups/s, a single worker falls 4,000,000 events/s behind and the backlog grows without bound.

What flips at this scale

The cost is O(n + m), so the question is which side changes. Events are partitioned by SKU across at least 5 workers, so each handles about 1,000,000 events/s and holds only its slice of the watchlist set.

The trade-off you'd defend

I would defend a partitioned set per worker over one big shared structure, trading the work of routing events by key for throughput that scales with workers and no cross-worker locking.

Illustrative figures; not Flipkart-published numbers.

Gotchas

A slice inside a loop

Symptom

A function that "walks the list once" slows quadratically.

Cause

items[i:] copies up to n elements each time, so the loop copies about n²/2 items.

Fix

Pass indices, or use itertools.islice for a lazy window.

Membership on a list inside a loop

Symptom

Runtime grows about 100× when rows grow 10×, with no extra I/O.

Cause

x in list is a linear scan (O(n) in the CPython docs), so the loop is O(n·m).

Fix

Convert to a set or dict once, outside the loop.

Tricky questions

Two pointers in nested loops are always quadratic
Most people say

A while inside a for, both over the same array, means n².

Actually

If both indices only move forward and never reset, total moves are at most 2n. Count pointer movement, not nesting.

Scenario question

A teammate calls a 15-line function "O(n)" because it has one for loop. Review it.

Model answer

I'd write the cost beside each line before agreeing, and look inside the loop for a list membership test, a slice, a sort or a scanning helper. If one is linear the function is quadratic, and I'd name both sizes. I'd suggest a set or an index. The trade-off is a one-time build and extra memory against removing a factor of the input size.

Interview corner

CommonWhat is the complexity of a loop with a slice inside it?
“I'd say O(n²) in total, because each slice copies up to n elements and the loop runs n times. I'd rewrite it with indices.”
TrickIs sorted(strings) O(n log n)?
“I'd say O(n log n) comparisons, but each string comparison can cost O(L), so character work is up to L times larger. I'd state that assumption.”
Experience checkWhere have you seen a hidden linear call inside a loop?
“I'd talk about list membership in a dedupe step. Building a set once changed the work from n times m to n plus m.”

Memory hook

A postman's workload is doors visited times the work at each door, not the number of streets.

If you remember only one thing:

Cost is how often each unit of work can run times what one run costs, including what the built-ins do.

Self-check

  1. What does for j in range(i) inside for i in range(n) cost?

    n(n-1)/2 iterations, which is Theta(n²).

  2. Why use separate variables for two input sizes?

    The answer is O(n·m) or O(n+m), and one letter hides which input drives it.

  3. Name three hidden linear costs in Python.

    x in list, slicing, and insert(0, x) or pop(0).

Prove it

Add a sort-then-scan function to the Key example. Run all three for n = 200, 400 and 800 and paste the n, eq_calls table. Success means the list version quadruples when n doubles, the set version stays at zero, and the sort version stays near n log n.

dsa-02-03Card 3 of 6

Read the common-complexity table

EasyP1 · Must knowKnow cold7 min
complexitygrowthtableinput-size

Why you care

When an interviewer says "n is up to 100,000", they are telling you which classes will pass. When a product manager says "ten times the merchants next year", they are asking the same thing. You need to know how each class grows and which are a wall. Interviewers also test the edges: output size, graphs with two sizes, and numeric value versus input length.

Explain like I'm 5

Think of walking, flying and teleporting. Doubling the distance doubles a walk (linear). A halving search is like a flight that barely notices distance (logarithmic). Squaring is visiting every house from every house.

Core concept

Read each class as "what happens to the work if the input doubles":

ClassDoubling n doesTypical source
O(1)nothingindex, dict lookup (average)
O(log n)adds one stephalving a sorted range
O(n)doublesone pass
O(n log n)a bit more than doublessorting
O(n²)quadruplesall pairs
O(n³)8×triple loop
O(2ⁿ)squares the workall subsets
O(n!)n+1 multiplies work by n+1; doubling n is astronomically worseall orderings

How far each class reaches depends on a step budget you state aloud; there is no universal operations-per-second figure. Translate constraints into feasible complexity shows how to pick one.

  • Output size is a lower bound. Producing k items takes at least k steps, so all pairs of n items is Omega(n²).
  • Graphs have two sizes. Traversal is O(V + E); an adjacency matrix costs O(V²) space.
  • Value versus input length. A DP table over capacity W costs n × W cells, but W = 10⁹ is only 30 bits of input. This is pseudo-polynomial.

Decision rule: estimate steps with the real sizes, compare with the stated budget, take the simplest class that fits. If none fits, change the algorithm, not the constants.

Minimal example The same n in four classes

PythonGrowth at n = 1000runs
import math
n = 1000
rows = {"n": n, "n log n": round(n * math.log2(n)), "n^2": n**2, "n^3": n**3}
for name, steps in rows.items():
    print(f"{name:8} {steps:>14,}")
print("2^n has", len(str(2**n)), "digits")
Output
n                 1,000
n log n           9,966
n^2           1,000,000
n^3       1,000,000,000
2^n has 302 digits

In production Which classes fit a stated budget

The budget is an assumption you declare, not a measurement. The block also shows a value-sized table and a dense graph.

PythonClassify candidate costs against a declared budgetruns
import math

BUDGET = 10**8  # steps you declare up front; an assumption, not a measurement
COSTS = {
    "n": lambda n: n,
    "n log n": lambda n: n * math.log2(n),
    "n^2": lambda n: n**2,
    "n^3": lambda n: n**3,
    "2^n": lambda n: 2**n,
    "n!": lambda n: math.factorial(n),
}


def verdicts(n, budget=BUDGET):
    return [name for name, f in COSTS.items() if f(n) <= budget]


for n in (10, 20, 1_000, 100_000):
    print(f"n={n:<7} fits: {', '.join(verdicts(n)) or 'nothing'}")

# Pseudo-polynomial: a table over capacity W costs n * W cells.
items, capacity = 100, 10**9
print("table cells:", f"{items * capacity:,}", "fits:", items * capacity <= BUDGET)
print("input size in bits for W:", capacity.bit_length())

# Graph: cost is a function of V and E, not one n.
V, E = 100_000, 300_000
print("V+E:", V + E, "V^2:", f"{V**2:,}", "V^2 fits:", V**2 <= BUDGET)
Output
n=10      fits: n, n log n, n^2, n^3, 2^n, n!
n=20      fits: n, n log n, n^2, n^3, 2^n
n=1000    fits: n, n log n, n^2
n=100000  fits: n, n log n
table cells: 100,000,000,000 fits: False
input size in bits for W: 30
V+E: 400000 V^2: 10,000,000,000 V^2 fits: False
Scenario A

In your world

The situation

Finance asks whether your reconciliation job survives the new region. Today it matches 48,213 transactions with a pairwise loop; volume is expected to grow tenfold. The Jenkins window is 30 minutes.

What actually breaks

Pairwise work is about n²: 48,213² ≈ 2.3×10⁹ today and 482,130² ≈ 2.3×10¹¹ after growth, 100 times more.

What you'd do on Monday

Put the growth ratio in the PR: 10× in n is 100× for a quadratic step and about 12× for n log n. Add a guard before the quadratic step that fails early.

PythonFail early when the budget is exceeded
STEP_BUDGET = 5 * 10**8   # declared and reviewed, not measured

def check_budget(n):
    if n * n > STEP_BUDGET:
        raise RuntimeError(f"pairwise step needs {n*n:,} > budget {STEP_BUDGET:,}")
Scenario B

Imagine you work at Cloudflare

1M requests/s against rule sets

The numbers

Illustrative: an edge cluster handles 1,000,000 requests/s and evaluates 200 rules per request: 1,000,000 × 200 = 2×10⁸ checks/s. Against a declared budget of 10⁸/s for this stage, a linear scan does not fit. Indexing rules by host leaves about 5 candidates: 1,000,000 × (1 lookup + 5 checks) = 6×10⁶. At 2,000 rules a linear scan needs 2×10⁹/s.

What the Scenario-A answer does here

The Scenario A fix (guard against a declared budget) still applies, but one n no longer describes the job. Requests and rules are independent sizes and a scan multiplies them: doubling either doubles the cost, doubling both quadruples it.

What flips at this scale

The goal becomes keeping candidates per request small and independent of total rule count. Rules are compiled into an index at deploy time, so per-request work depends on how many rules share a host.

The trade-off you'd defend

I would defend a precomputed index over a flat rule list, trading build time and memory at deploy for per-request work that stays flat as rules grow.

Illustrative figures chosen for the arithmetic; not Cloudflare-published numbers.

Gotchas

Treating a numeric value as the input size

Symptom

A "polynomial" solution allocates a billion-cell table for a 30-bit number and is OOM-killed.

Cause

Cost depends on the value W, while input size is log W bits.

Fix

Check W against memory first, cap it, or choose a method whose cost depends on n.

One n for a graph

Symptom

A traversal quoted as O(n) is far slower on dense data.

Cause

Cost is O(V + E), and for dense data E approaches V².

Fix

Quote V and E separately and say whether the graph is sparse.

Tricky questions

O(n log n) and O(n²) are both polynomial, so the gap is small
Most people say

Both are efficient, so pick the one that is easier to write.

Actually

At n = 1,000,000, n log n is about 2×10⁷ steps and n² is 10¹². The gap grows with n, and at that size only one fits.

Scenario question

You're handed a spec that says "n up to 200,000" and a draft solution with a triple loop. What do you do?

Model answer

I'd count first: 200,000³ is 8×10¹⁵, far beyond any budget I would declare, and n² is 4×10¹⁰, still too large. I'd look for something near n log n, such as sort plus scan or hashing. The trade-off is that the faster design is harder to get right, so I'd keep the cubic version as a test oracle for small inputs.

Interview corner

Commonn is 100,000. Is O(n²) acceptable?
“I'd say not without more information: 10¹⁰ steps is past what I would budget. I'd aim for n log n and say the budget I assumed.”
TrickIs a knapsack-style DP over capacity W polynomial?
“I'd say pseudo-polynomial. It costs n times W, but W is a value and the input only has log W bits.”
DesignHow do you choose between an adjacency list and a matrix?
“I'd compare E with V². Sparse graphs get the list, with O(V+E) space; dense graphs can afford the matrix and its O(1) edge lookup at O(V²) space.”

Memory hook

Walking, flying, teleporting: the table ranks how badly each class reacts when you double the trip.

If you remember only one thing:

Classes tell you how work grows; a declared budget tells you whether it fits.

Self-check

  1. What happens to O(n²) work when n doubles?

    It quadruples.

  2. Why is output size a lower bound?

    Producing k items takes at least k steps.

  3. Why is an n × W table not truly polynomial?

    W is a value whose input length is log W bits.

Prove it

Extend the production example to print n log n and n^2 at n = 10³, 10⁴, 10⁵ and 10⁶ with the same budget. Paste the output. Success means you can name the first n where n^2 stops fitting and what that means for your algorithm choice.

dsa-02-04Card 4 of 6

Account for auxiliary and output space

MediumP2 · Very likelyKnow cold7 min
spaceauxiliarymemorycopies

Why you care

Memory limits kill jobs differently from time limits. An agent with 4 GB does not get slower; it is killed with exit code 137 and a log that stops mid-line. You need to know how many copies of your data exist at the peak. Interviewers ask for space complexity because the honest answer needs three numbers.

Explain like I'm 5

Picture a workbench. The parts you were handed are the input. Any extra tray you pull out is auxiliary space. The finished box you hand back is the output. A lazy answer counts only the trays; a careful one asks how many were out at once.

Core concept

Name which part of space you mean:

  • Input space: what the caller holds. You may not be allowed to change it.
  • Auxiliary space: extra memory beyond input and output: visited sets, queues, heaps, DP tables, recursion frames, temporary copies.
  • Output space: what you return; k items need at least k. Say whether you count it.

Rules that catch people:

  • Count the peak, not the total. A temporary freed before the next allocation does not add; two alive together do.
  • Slices copy. items[1:] allocates a new list of n-1 pointers. A shallow copy duplicates the container, not the elements.
  • Structures grow with what they hold: a visited set or queue up to O(V), a DP table one cell per state, a bounded heap O(K).
  • In place is not automatically O(1). The Python time-complexity page gives no space figure for list.sort, so do not claim O(1) for code that calls it.

Decision rule: report auxiliary and output space separately, find the moment the most structures are alive, and claim O(1) only when every temporary is a fixed number of scalars. Mutate in place only when the caller allows it.

Minimal example A slice allocates a new pointer block

PythonOne slice, one new listruns
import tracemalloc
a = list(range(100_000))
print(a[:] is a, a[:][0] is a[0])
tracemalloc.start()
tail = a[1:]
live = tracemalloc.get_traced_memory()[0]
tracemalloc.stop()
print(len(tail), live > 700_000)
Output
False True
99999 True

In production Three ways to deduplicate, three peaks

All three return the same unique ids. The set grows with distinct values, the sorted copy duplicates the input, and the in-place version needs permission to mutate. Peaks are compared, not printed, so the output is stable.

PythonCompare peak allocationsruns
import random
import tracemalloc

random.seed(7)
ids = [random.randrange(20_000) for _ in range(50_000)]


def with_set(xs):
    seen = set()
    return [x for x in xs if not (x in seen or seen.add(x))]


def sorted_copy(xs):
    out = []
    for x in sorted(xs):
        if not out or out[-1] != x:
            out.append(x)
    return out


def in_place(xs):
    xs.sort()
    w = 0
    for r in range(len(xs)):
        if w == 0 or xs[r] != xs[w - 1]:
            xs[w] = xs[r]
            w += 1
    del xs[w:]
    return xs


def peak(fn, data):
    tracemalloc.start()
    res = fn(data)
    _, p = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return res, p


r1, p1 = peak(with_set, list(ids))
r2, p2 = peak(sorted_copy, list(ids))
r3, p3 = peak(in_place, list(ids))
print(len(r1), len(r2), len(r3), sorted(r1) == r2 == r3)
print("set bigger than in-place:", p1 > p3)
print("sorted copy bigger than in-place:", p2 > p3)
Output
18297 18297 18297 True
set bigger than in-place: True
sorted copy bigger than in-place: True
Scenario A

In your world

The situation

Your job downloads a 1.2 GB CSV from S3 into a list of rows, drops the header with rows[1:], sorts a copy by settled_at, and builds a dict by txn_id. The Jenkins agent has a 4 GB container limit.

What actually breaks

At the peak the original list, the slice, the sorted copy and the dict are all alive. The container is killed, Jenkins reports exit code 137, and the audit table shows 0 rows written.

What you'd do on Monday

Name each allocation and when it dies, then remove the copies that need not exist: skip the header with an iterator, sort in place if allowed, and build the dict only if you need random access.

PythonSkip the header and sort without extra copies
import csv

with open(path, newline="") as f:
    reader = csv.reader(f)
    next(reader)                       # header, no slice
    rows = list(reader)                # one copy of the rows
rows.sort(key=lambda r: r[4])          # in place: allowed, the data is ours
Scenario B

Imagine you work at Meesho

20M listing ids per nightly dedupe

The numbers

Illustrative: 20,000,000 listing ids as Python ints. The list holds 20,000,000 × 8 B = 160 MB of pointers and the int objects add about 20,000,000 × 32 B = 640 MB. A seen-set at about two slots per entry has 40,000,000 slots × 16 B (hash plus pointer) = 640 MB. The unique output list is up to 160 MB. Peak ≈ 160 + 640 + 640 + 160 = 1,600 MB.

What the Scenario-A answer does here

The Scenario A fix (drop needless copies) still removes slice-sized waste. It does not touch the seen-set, which scales with distinct values and dominates the peak at 640 MB.

What flips at this scale

The dedupe is partitioned: ids go to 16 shards by id % 16, each processed alone. A shard holds about 1,250,000 ids, so its set has about 2,500,000 slots × 16 B = 40 MB. Peak auxiliary memory falls from 640 MB to about 40 MB, for one extra partitioning pass.

The trade-off you'd defend

I would defend sharded processing over one global set, trading an extra pass and more moving parts for a memory ceiling that does not move when the catalogue grows.

Illustrative sizes and per-object byte figures; not Meesho-published numbers.

Gotchas

"In place" claimed as O(1) space

Symptom

A function documented as O(1) space is OOM-killed on a large input.

Cause

It sorts, builds a dict of seen values or recurses; each grows with the input.

Fix

List every temporary and when it dies; claim O(1) only if scalars remain.

Shallow copy shares elements

Symptom

Editing a row in the "copy" also changes the original.

Cause

list(rows) and rows[:] copy pointers, not row objects.

Fix

Copy rows deliberately (for example dict(r)) when you need independence, and count that cost.

Tricky questions

Slicing is free because Python does not copy objects
Most people say

A slice only creates a view.

Actually

A list slice builds a new list with copied pointers, O(k) time and space for k elements. Only the element objects are shared.

Scenario question

You're handed a job killed with exit 137 on a 4 GB agent. It holds a list of rows, a slice, a sorted copy and a dict. Where do you start?

Model answer

I'd measure first with tracemalloc or by logging process memory after each stage, so I know which allocation is the peak. Then I'd remove copies that are not needed, such as the slice, and sort in place if allowed. The trade-off is memory against fast random access from the dict.

Interview corner

CommonWhat is the space complexity of your solution?
“I'd give auxiliary space and say whether I count output, for example "O(V) auxiliary for the visited set and queue, plus the output list".”
TrickDoes an in-place algorithm use O(1) space?
“I'd say not automatically. A recursion stack, a hash set or a sort can still add memory, so I'd check each temporary first.”
Experience checkHave you hit an out-of-memory failure on a job?
“I'd describe a pipeline holding rows, a sorted copy and a lookup dict at once. I fixed it by streaming and now check peaks with tracemalloc.”

Memory hook

The workbench has a fixed size, so count the trays out at the same moment.

If you remember only one thing:

Space is the peak of what is alive at once, split into input, auxiliary and output.

Self-check

  1. What are the three parts of space accounting?

    Input, auxiliary and output space.

  2. Does rows[1:] copy the row objects?

    No; it copies pointers into a new list, and the row objects are shared.

  3. Why is "in place" not enough for O(1) auxiliary space?

    Recursion frames, sort workspace or a seen-dict can still grow.

Prove it

Run the three dedupe functions on 50,000, 100,000 and 200,000 ids under tracemalloc and paste each peak in KiB. Success means the set and sorted-copy peaks grow with n, the in-place peak stays far smaller, and you can say which temporary caused each.

dsa-02-05Card 5 of 6

Count recursive calls and stack depth separately

MediumP2 · Very likelyKnow cold8 min
recursionrecurrencestack-depthmemoization

Why you care

Recursive code hides two costs. Total calls drive time. Calls alive at once drive stack, and in Python they also decide whether the program crashes: CPython's default recursion limit is 1,000 frames, so deep input raises RecursionError long before memory runs out. Interviewers ask for both numbers.

Explain like I'm 5

Think of a to-do list where finishing a task can add sub-tasks. The job's length depends on how many tasks you complete in total. What you must remember depends on how many half-finished tasks are stacked at once.

Core concept

Compute two numbers and keep them apart:

  • Time = total calls × work per call. Count calls from a recurrence or the call tree.
  • Stack = maximum live depth × frame size. Live depth is the longest root-to-leaf path, not the call count.

Common shapes:

  • Linear chain: f(n) calls f(n-1) once: O(n) time, O(n) stack.
  • Divide and conquer: T(n) = 2T(n/2) + n. Each level does n work over log₂ n levels: O(n log n) time, O(log n) depth.
  • Unbalanced split: if one side keeps one element, T(n) = T(n-1) + n gives O(n²) time, O(n) depth. Do not assume balance.
  • Branching search: b children to depth d is about b^d calls, depth d.
  • Memoized recursion: time is distinct states times transitions per state; the cache holds one entry per state.

Decision rule: write the recurrence for calls, solve it by level sums, state depth separately, and ask which input makes the tree a chain. Switch to an explicit stack when worst-case depth can pass the runtime limit; it costs O(depth) heap entries.

Minimal example Calls grow exponentially, depth does not

PythonBranching 2, depth 10runs
calls = depth = max_depth = 0
def walk(level, branching):
    global calls, depth, max_depth
    calls += 1
    depth += 1
    max_depth = max(max_depth, depth)
    if level:
        for _ in range(branching):
            walk(level - 1, branching)
    depth -= 1
walk(10, 2)
print("calls", calls, "max live depth", max_depth)
print(calls == 2**11 - 1)
Output
calls 2047 max live depth 11
True

In production Same recurrence, balanced versus skewed splits

Halving gives about n log n work and log n depth. Peeling one element off gives quadratic work and linear depth, and a large enough n crosses the recursion limit.

PythonCalls, work and depth for two split shapesruns
import sys


def analyse(n, split):
    """Count calls, per-call work and live depth for a size-n split recursion."""
    stats = {"calls": 0, "work": 0, "depth": 0, "max_depth": 0}

    def go(size):
        stats["calls"] += 1
        stats["depth"] += 1
        stats["max_depth"] = max(stats["max_depth"], stats["depth"])
        if size > 1:
            stats["work"] += size          # partition/merge cost at this call
            left = split(size)
            go(left)
            go(size - left)
        stats["depth"] -= 1

    go(n)
    return stats


halves = lambda s: s // 2
worst = lambda s: 1

print("limit", sys.getrecursionlimit())
print("balanced", analyse(1024, halves))
try:
    print("skewed", analyse(300, worst))
    analyse(5000, worst)
except RecursionError as e:
    print("RecursionError:", str(e)[:32])
Output
limit 1000
balanced {'calls': 2047, 'work': 10240, 'depth': 0, 'max_depth': 11}
skewed {'calls': 599, 'work': 45149, 'depth': 0, 'max_depth': 300}
RecursionError: maximum recursion depth exceeded

See it happen Calls accumulate, the stack comes and goes

live stack (depth 3 max)rootRRRcalls so far7
  1. The root call starts: one frame is live and one call has been made.
  2. The left child starts: stack depth is 2 and the call count is 2.
  3. The left-left leaf runs: depth peaks at 3 after three calls.
  4. The leaf returns and its sibling reuses the same slot, so depth stays 3 while calls reach 4.
  5. The left subtree is done; the right child begins and the count is 5.
  6. By the end there have been 7 calls but never more than 3 frames alive.
Notice: the call counter only climbs while the stack row reuses the same slots, which is why time and stack need separate answers.
Scenario A

In your world

The situation

A job flattens a category hierarchy with a recursive path(cat_id) that follows parent_id upwards, wrapped in except Exception that logs a warning. There are 48,213 categories.

What actually breaks

A bad import left a three-category cycle. The function hit 1,000 frames, RecursionError was swallowed, and 312 categories were skipped. The build stayed green, the audit logged 48,213 read and 47,901 written, and finance found the gap a week later.

What you'd do on Monday

Make depth explicit and visited-aware. An iterative walk with a visited set costs O(depth), raises a precise error on a cycle and has no recursion limit.

PythonIterative walk with cycle detection
def path(cat_id, parent_of):
    seen, out = set(), []
    while cat_id is not None:
        if cat_id in seen:
            raise ValueError(f"cycle at category {cat_id}")
        seen.add(cat_id)
        out.append(cat_id)
        cat_id = parent_of.get(cat_id)
    return out
Scenario B

Imagine you work at Datadog

50,000-span traces

The numbers

Illustrative: most traces have about 200 spans and depth near 30, but a retry loop produces chain-shaped traces of 50,000 spans, each the parent of the next. A recursive walk makes 50,000 calls and holds 50,000 live frames at the deepest point; CPython's default limit is 1,000. An explicit stack with one entry per pending span is at most 50,000 × 8 B = 400 KB.

What the Scenario-A answer does here

The Scenario A fix (an iterative walk) is the right shape and still works. What breaks is assuming depth is small: balanced test traces pass, and the chain-shaped one carries the incident.

What flips at this scale

Time stays O(n); the change is entirely in the stack. State moves to the heap, so depth is bounded by memory you can budget rather than by the interpreter, and depth is logged as a metric.

The trade-off you'd defend

I would defend an explicit stack over raising the recursion limit, trading slightly less readable code for a failure mode I can bound and monitor instead of a crash at a deep frame.

Illustrative trace sizes; not Datadog-published figures.

Gotchas

Recursion limit reached on a chain

Symptom

RecursionError: maximum recursion depth exceeded on a long hierarchy while small test data passes.

Cause

Live depth equals chain length, and CPython's default limit is 1,000 frames.

Fix

Use an explicit stack or loop, or bound input depth and fail with a clear message.

Assuming the split is balanced

Symptom

A routine quoted as O(n log n) takes quadratic time on sorted input.

Cause

With a bad split the recurrence is T(n) = T(n-1) + n.

Fix

State the split assumption or choose the split so it cannot degrade.

Tricky questions

The recursion makes 2047 calls, so the stack needs 2047 frames
Most people say

Stack is the number of calls.

Actually

Frames are freed as calls return. Stack is the longest chain alive at once, here 11. Time counts all calls; space counts the deepest path.

Scenario question

You're handed a recursive function over a hierarchy that passes tests and raises RecursionError in production. What do you do?

Model answer

I'd measure depth on the failing input, since it is probably a chain or a cycle the tests never covered. Then I'd rewrite the walk as a loop with an explicit stack and a visited set, making depth a heap cost. The trade-off is less natural code against not depending on a limit I cannot control.

Interview corner

CommonWhat is the time and space of a recursive function?
“I'd say time is total calls times work per call, and space is maximum live depth. I'd get calls from a recurrence and depth from the longest root-to-leaf path.”
TrickQuick sort is O(n log n), so its stack is O(log n)?
“I'd say that holds for balanced splits. With a bad pivot every time, depth is n and time is n². Recursing into the smaller side first limits stack.”
DesignWhen do you convert recursion to an explicit stack?
“I'd do it when worst-case depth can exceed the runtime limit or cycles are possible. The cost is a heap stack I can size and monitor.”

Memory hook

Count the tasks you finish for time, and the half-finished tasks stacked up for the stack.

If you remember only one thing:

Time comes from total calls and stack from maximum live depth; they are different numbers.

Self-check

  1. What decides stack usage in a recursive function?

    Maximum live depth, the longest chain of calls alive at once.

  2. What is T(n) for halving with linear work per call?

    O(n log n), with depth O(log n).

  3. How is memoized recursion costed?

    Distinct states times transitions per state, plus one cache entry per state.

Prove it

Run analyse with the halving split for n = 2⁴, 2⁸ and 2¹², and the skewed split for n = 100, 200 and 400. Paste n, calls, work, max_depth for each. Success means balanced work tracks n log n, skewed work tracks n²/2, and depth tracks log n versus n.

dsa-02-06Card 6 of 6

Know when quadratic work is acceptable

EasyP2 · Very likelyTalk about it7 min
quadratictrade-offsbudgetsimplicity

Why you care

Teams lose a week replacing a perfectly good O(n²) loop with something clever, then ship a bug in the clever version. The opposite failure is shipping a quadratic loop on an input that was supposed to be small and is not. Interviewers ask for brute force first, then ask when it is good enough.

Explain like I'm 5

A shopkeeper with twelve items on the shelf does not build a barcode system; she looks at each one. A warehouse with a million items needs the system. The mistake is not counting.

Core concept

Quadratic work is acceptable when you can show these:

  • The input is bounded and the bound is enforced. A batch capped at 500 costs at most 500² = 250,000 steps.
  • The cost fits a declared budget. Compute n², compare it with a budget you state, and keep the arithmetic in review. Derive steps; do not invent timings.
  • The output is itself quadratic. Emitting every pair needs n(n-1)/2 results.
  • The simple version is the baseline and the oracle for testing a faster one on random small inputs.
  • The faster version has real risk: tie-breaking, duplicates and ordering.

It is not acceptable when n is unbounded or the stated limit exceeds the budget.

A nested loop builds nothing, while a hash version spends memory and rests on an average-case assumption. Do not quote either as a measured speed without measuring.

Decision rule: accept quadratic work when n has an enforced cap, the step count fits a written budget, and the simpler code lowers correctness risk. Otherwise move down the table in Read the common-complexity table.

Minimal example All pairs is n(n-1)/2

PythonCount pairsruns
n = 100
pairs = sum(1 for i in range(n) for j in range(i + 1, n))
print(pairs, n * (n - 1) // 2)
budget = 5_000
print(pairs <= budget)
print("budget used:", round(pairs / budget, 2))
Output
4950 4950
True
budget used: 0.99

In production Quadratic baseline as oracle, with a size guard

The quadratic version is the reference and the hashed version is the candidate. The check compares them on 200 seeded random batches, and plan states when the quadratic version is allowed.

PythonBaseline, candidate and a budget checkruns
import random

random.seed(3)


def match_quadratic(refunds, payments):
    return sorted((r, p) for r, ra in refunds for p, pa in payments if ra == pa)


def match_hashed(refunds, payments):
    by_amount = {}
    for p, pa in payments:
        by_amount.setdefault(pa, []).append(p)
    return sorted((r, p) for r, ra in refunds for p in by_amount.get(ra, []))


def plan(n, budget):
    steps = n * n
    return {"n": n, "steps": steps, "quadratic_ok": steps <= budget}


for trial in range(200):
    k = random.randrange(0, 40)
    refunds = [(f"R{i}", random.randrange(10)) for i in range(k)]
    payments = [(f"P{i}", random.randrange(10)) for i in range(k)]
    assert match_quadratic(refunds, payments) == match_hashed(refunds, payments)
print("200 random batches: both versions agree")

BATCH_CAP = 500
print(plan(BATCH_CAP, budget=1_000_000))
print(plan(2_000_000, budget=1_000_000))
Output
200 random batches: both versions agree
{'n': 500, 'steps': 250000, 'quadratic_ok': True}
{'n': 2000000, 'steps': 4000000000000, 'quadratic_ok': False}
Scenario A

In your world

The situation

A daily report cross-checks 400 merchants against 300 fee rules with nested loops. A teammate wants to replace it with an index, which will take a week and change the output order.

What actually breaks

The optimised version dropped merchants that matched no rule, because a dictionary get returned nothing and the loop skipped them. 17 merchants vanished on a green build. The original did 400 × 300 = 120,000 comparisons.

What you'd do on Monday

Keep the loop, write the bound and budget next to it, and fail loudly if input grows past the cap.

PythonA documented quadratic loop with a guard
MAX_MERCHANTS, MAX_RULES = 5_000, 2_000     # 10M steps, reviewed budget 50M

def apply_rules(merchants, rules):
    if len(merchants) > MAX_MERCHANTS or len(rules) > MAX_RULES:
        raise ValueError("input exceeds the quadratic budget; revisit the design")
    # O(M*R): bounded above; kept simple on purpose
    return [(m, [r for r in rules if r.matches(m)]) for m in merchants]
Scenario B

Imagine you work at Zomato

60 orders per zone window vs a citywide batch

The numbers

Illustrative: orders are grouped by zone and a 30-second window. A zone window has at most 60 orders, so a pairwise compatibility check is 60 × 59 / 2 = 1,770 pairs. With 1,000 zones that is 1,770,000 pair checks per window. Across a citywide batch of 60,000 orders it would be 60,000 × 59,999 / 2 ≈ 1.8×10⁹.

What the Scenario-A answer does here

The Scenario A fix (cap and guard) still applies, inside a zone. The assumption that n is small holds for a zone window and fails for the city, and merging windows for convenience turns 1.77 million checks into 1.8 billion.

What flips at this scale

The quadratic step stays, but its input is bounded by construction: orders are bucketed by zone and window before pairing, so n is capped by bucket size. An oversized bucket is split rather than run slowly.

The trade-off you'd defend

I would defend a bounded quadratic step inside buckets over a more elaborate global structure, trading some wasted pair checks for code that is easy to verify, as long as the cap is enforced.

Illustrative window sizes and counts; not Zomato-published figures.

Gotchas

A cap that nobody enforces

Symptom

A "small" quadratic step takes hours after a data change, with no error.

Cause

The bound lived in someone's head and nothing checked it.

Fix

Raise an exception with the actual size when the cap is exceeded.

Replacing the simple version without an oracle

Symptom

The faster version passes the sample, then drops rows in production.

Cause

The simple loop handled unmatched items by accident.

Fix

Keep the quadratic version as a reference and compare outputs on random small inputs.

Tricky questions

A hash-based version is always faster
Most people say

Hashing is O(1), so it always beats a nested loop.

Actually

Hashing is average-case, costs memory, and has overhead that matters on tiny inputs. Faster at scale does not mean faster at n = 20; measure if the decision depends on it.

Scenario question

You're handed a 30-line function with nested loops over two lists, each at most a few hundred items. A reviewer asks for an O(n) rewrite. What do you say?

Model answer

I'd ask how the lists are bounded and whether anything enforces it. If both are capped at a few hundred, the step count is around 100,000, far inside any budget I would write down. I'd keep the loop, add a guard that raises past the cap, and rewrite only if the cap is not real. The trade-off is a few extra comparisons against less code to review and fewer correctness bugs.

Interview corner

CommonWhen is an O(n²) solution acceptable?
“I'd say when n is small and bounded, when the output is quadratic anyway, or when a simpler baseline fits an explicit budget.”
TrickIs an O(n) hash solution always better than an O(n²) loop?
“I'd say not always. The hash version costs memory and rests on an average-case assumption, and for tiny inputs the loop is simpler. At the stated limit I'd check the arithmetic.”
DesignHow would you make a quadratic step safe in production?
“I'd enforce a cap with an error that prints the size, bucket the input so the cap holds by construction, and keep the quadratic version as an oracle for any faster replacement.”

Memory hook

The corner shop looks at each item; the warehouse needs a system, and the mistake is not counting.

If you remember only one thing:

Quadratic is fine only with an enforced bound, a written budget and the arithmetic to show it.

Self-check

  1. How many pairs do n items have?

    n(n-1)/2.

  2. Name three situations where O(n²) is acceptable.

    A small enforced cap, a required quadratic output, or a simple baseline within a stated budget.

  3. Why keep the quadratic version after writing a faster one?

    It is a test oracle on random small inputs.

Prove it

Assert that match_quadratic and match_hashed agree on 1,000 seeded batches including empty ones and heavy duplicates. Then print plan(n, budget) for n = 500, 5,000 and 50,000 with a budget of 10⁷ and paste the output. Success means the assertion passes and the plan flips from True to False at a threshold you can name.