Complexity and Constraint Analysis

The constraint that changes the answer

Suppose an interviewer gives you an array and asks for the sum between two indexes. A scan from left to right is difficult to improve upon as a first answer. It uses constant extra space, does no preparation, and takes linear time in the length of the requested range.

Then the interviewer adds one fact: there will be 100,000 queries over the same array.

The algorithm has not become incorrect, but it has become badly matched to the work. If the array has n values and there are q queries, repeated scans cost O(qn) in the worst case. A prefix-sum array costs O(n) time and space to build, then answers each query in O(1), for O(n + q) total time. Memory has bought the removal of repeated work.

Now allow updates between queries. One changed value invalidates every later prefix sum, so the earlier optimization has acquired an expensive operation. A Fenwick tree or segment tree spends O(n) space and makes both updates and queries O(log n). That is slower than a prefix array for a query, much faster for an update, and better for the workload now described.

Complexity analysis begins here, before code: identify what can grow, what the program must do repeatedly, and what state it may keep. The right design is the simplest one that fits those constraints.

Describe the execution, not the syntax

A credible cost model has three parts.

First, name the independent dimensions. n is not a universal synonym for input. Two arrays may have lengths n and m, making a nested comparison O(nm), not necessarily O(n²). A graph has V vertices and E edges. A grid has R rows and C columns. A query workload has both data size n and query count q. A top-k result has an output dimension k. Backtracking has a branching factor and a depth.

Second, count the operations that grow. Include the work hidden inside a loop: sorting, heap adjustment, map access, slicing, string construction, comparison, allocation, copying, and calls into a library. One visible loop is not linear when its body copies a prefix whose length grows on every iteration.

Third, account for the state that remains alive. Separate working memory from the recursive call stack and from returned output when the distinction is useful. A breadth-first traversal may visit each node once yet hold an entire level in its queue. A recursive tree walk may allocate no explicit collection but still keep one frame per node on a long path. An algorithm that returns all permutations cannot use less time or output space than those permutations themselves occupy.

This is why “the traversal is linear” is too vague. A useful account sounds like this:

Let V be the number of vertices and E the number of edges. Breadth-first search enqueues each vertex at most once and inspects each edge once, so it takes O(V + E) time. The visited set and queue use O(V) auxiliary space.

The sentence follows the execution: variables, operations, retained state.

Let scale reject ideas early

Constraints are estimates of design pressure, not promises about elapsed time. Machine speed, language, input distribution, and operation cost still matter. Even so, growth rates eliminate implausible approaches quickly.

When n is near 20, enumerating subsets may be intended; enumerating all permutations still needs a reason. At a few hundred items, a clear quadratic dynamic program can be entirely sensible. At hundreds of thousands, pairwise comparison is usually finished as a candidate before implementation begins. When values reach 10^9, iteration over the value range is suspect even if the number of values is small. When a graph can be dense, saying “linear” without naming both V and E hides a possible quadratic edge count.

Do not memorize these bands as a timing chart. Use them to ask what work the prompt can afford. If n = 200,000, O(n log n) sorting may be an excellent purchase: it can make duplicates adjacent, enable two pointers, or reduce interval relationships to a single scan. If n = 500, a simpler O(n²) solution may be safer than a fragile optimization. Asymptotic improvement is not the same as engineering improvement when both designs fit comfortably.

Value bounds carry design information too. A million values drawn from [0, 1000] invite counting or buckets. A few values as large as 10^9 do not invite an array indexed by value. A large numeric answer range may suggest binary search on the answer rather than enumeration. Read every dimension the prompt gives you; one often explains why the obvious structure is wrong.

Find the repeated work

A baseline is useful because it exposes the operation worth removing. In two sum, checking every pair costs O(n²) time and constant auxiliary space. The repeated work is searching the remaining values for a complement. A map buys one-pass lookup with O(n) space and expected O(n) time.

The same reasoning makes the expected-linear solution to longest consecutive sequence more than a remembered trick. Put all n values in a set. Expand forward from x only when x - 1 is absent.

That start condition is the cost proof. Without it, the input [1, 2, 3, ..., n] can be rescanned from every value and take O(n²) time. With it, each value participates in at most one expansion. Building the set and performing the expansions therefore take expected O(n) total time and O(n) space. Sorting first gives a deterministic O(n log n) alternative with different memory details.

Notice the qualifier expected. The set version assumes expected O(1) membership. A bound is only as strong as the operation guarantees underneath it.

Say which guarantee you mean

Worst-case, expected, and amortized costs answer different questions.

Worst-case analysis asks for the largest cost among inputs of a given size. It keeps a favorable sample from disguising a bad shape: balanced-tree recursion may be shallow, while a skewed tree creates a chain of n active calls.

Expected analysis depends on a stated source of averaging, often randomized behavior or a data-structure assumption. Hash-table lookup is commonly treated as expected O(1), so a scan using a hash set is expected linear time. If the problem requires a deterministic worst-case guarantee, a balanced tree may change each lookup to O(log n) and the total to O(n log n). Quicksort, randomized selection, and input-dependent pruning require the same honesty about which result is being claimed.

Amortized analysis spreads occasional expensive maintenance across a sequence of operations without assuming random input. A dynamic array that grows geometrically sometimes copies all existing elements during append. Across n appends, however, the total number of copied elements is O(n), making an append O(1) amortized even though a particular append can be linear.

“Amortized” is not a rescue word for repeated copying. If an immutable string is rebuilt from its entire prefix on every loop iteration, the sum of copied lengths is commonly quadratic. If a recursive branch copies a path, that copy belongs in both the time and space account even when it is required for correctness.

Recursion has two separate shapes

Recursive time follows the search tree; stack space follows only the longest active chain. Confusing them produces both bad bounds and unsafe code.

Consider word search on an R × C board for a word of length L. The search may begin at every cell. From a matching start it has at most four choices, then at most three forward choices per step because the previous cell cannot be reused. A conventional upper bound is O(RC · 4 · 3^(L-1)), often shortened to O(RC · 3^L). The active call chain is only O(L) deep.

Marking a cell in place and restoring it can avoid a separate visited set, but it does not remove the call stack. Keeping a path set uses up to O(L) more working memory. Returning every valid path would add output whose size may itself be exponential.

Pruning can make real inputs dramatically faster: reject when L > RC, reject when the board lacks required letters, or begin from the rarer end when the contract permits reversal. None of those observations makes the worst-case search polynomial. They explain why an exponential algorithm can still be the right one when L is small and the search usually collapses early.

Depth also has a machine consequence that Big-O notation does not settle. Recursive DFS of a balanced tree may use O(log n) stack; the same code on a long path may use O(n) and exceed the runtime’s stack limit. An explicit stack can be the safer representation even when its asymptotic space is the same.

Audit the code you actually wrote

After implementation, revisit the model. This is where convenient operations often change the answer:

• slicing inside a loop may copy a growing number of elements;
• membership in an array-backed list may be a linear scan;
• removing the first array element may shift everything after it;
• a sort comparator may perform nonconstant work on each comparison;
• constructing composite string keys may repeatedly copy large values;
• a queue, heap, memo table, or saved path may grow farther than expected;
• output construction may dominate both time and memory.

Chapter 30 established that language semantics can break a correct idea. They can also break its complexity claim. Know whether an operation copies or views, whether a collection gives the guarantee you are using, and whether a built-in sort needs stack or buffer space. If that behavior varies by runtime, say so rather than inventing precision.

Once the asymptotic class fits, the machine matters. Allocation, locality, cache behavior, object overhead, numeric representation, and constant factors can decide between two viable designs. So can readability and the ease of proving correctness. Big-O removes designs that cannot scale; it does not rank every design that remains.

Close the analysis in one pass

At the end of a coding solution, walk the execution in order. Define the variables. Name setup work and the dominant repeated operations. State auxiliary space, then stack and output when they differ. Finish with any expected, amortized, or worst-case assumption that the bound needs.

For interval merging, a complete close is:

Let n be the number of intervals. Sorting by start takes O(n log n) and the merge scan takes O(n), so total time is O(n log n). The result may contain O(n) intervals. Excluding that output, the scan uses constant extra state; the sort may use additional stack or buffer space depending on the runtime.

Practice this analysis on code, not on algorithm names. Take an old solution and change one constraint at a time: add many queries, allow updates, forbid mutation, require deterministic worst-case time, make the graph dense, or require every answer rather than one. Then identify the first line of the cost model that changes.

The next chapter turns this judgment into live-round sequence. Constraint analysis belongs near the beginning of that sequence, where it can still change the plan—not only at the end, where it can merely describe the choice already made.

Related reading

• Chapter 19: The Six-Phase Response Loop
• Chapter 25: Communicating Trade-Offs Like a Senior Engineer
• Chapter 30: Interview-Language Fluency
• Chapter 32: The Coding-Round Workflow
• Chapter 33: Correctness Before Cleverness