Complexity analysis

Why it matters

Before writing code in an interview you should already know roughly how fast it will run and whether that is fast enough for the input limits. Complexity analysis gives you that prediction, lets you compare two designs without implementing both, and is the first thing an interviewer checks when you propose an approach. The same reasoning tells you in production whether a job survives ten times more data, or whether a "constant-time" lookup hides a linear scan.

Core ideas

Notation. O is an upper bound, Ω a lower bound, Θ both. In interviews "O" is usually read as a tight bound, so do not say O(n log n) if your code is O(n). Constants and lower-order terms are dropped, but they still decide between two solutions of the same class.

Which case you are stating.

• Worst case holds for every input of size n: binary search, merge sort, heap operations.
• Expected averages over the algorithm's own random choices, for every input: randomized quickselect, hashing with a randomly chosen hash function. It is not the same as average case, which averages over an assumed input distribution.
• Amortized bounds the total cost of any sequence of m operations, divided by m. A dynamic array that doubles its capacity copies 1 + 2 + 4 + ... < 2n elements over n appends, so append is amortized O(1), although the single append that triggers growth costs O(n). Amortized bounds are worst-case statements about sequences; no probability is involved.

Time versus space. Report auxiliary space (what you allocate beyond the input) and say whether the output counts. Recursion consumes stack: DFS on a path-shaped tree with n nodes is n frames deep even if it allocates nothing else, while merge sort recurses only O(log n) deep.

Several input dimensions. Do not collapse independent sizes into one n. A grid search is O(rows × cols); BFS over an adjacency list is O(V + E); merging k sorted lists of N total elements with a heap is O(N log k); comparing all pairs of n words of length up to L is O(n² × L). Hashing a string key costs O(L), not O(1).

Output-sensitive bounds. When the answer is large, the bound must include it. There are 2ⁿ subsets with average size n/2, so listing them is Θ(n × 2ⁿ) for any algorithm: no method can be faster than writing its output.

Recurrences. Draw the recursion tree and sum work per level. T(n) = 2T(n/2) + O(n) has log n levels of O(n) work: O(n log n). T(n) = T(n/2) + O(1) is O(log n). T(n) = T(n − 1) + O(n) sums to O(n²), which is why a recursion that passes a copied slice a[1:] is quadratic.

From limits to a target. A rough rule of thumb is around 10⁸ simple operations per second in compiled languages and roughly an order of magnitude fewer in CPython. So n near 10⁵ to 10⁶ calls for O(n log n) or better, n near 10³ to 10⁴ allows O(n²), and n up to about 20 allows O(2ⁿ × n). Use this as a sanity check, not a law.

Common misconceptions

• "Hash map operations are O(1)." They are expected O(1) under good hashing and a bounded load factor, plus the cost of hashing the key. Adversarial or degenerate keys make them O(n), and a resize makes an individual insert expensive.
• "Amortized means average over random inputs." It is a guarantee for every sequence of operations; individual operations may still be slow, which matters for latency-sensitive code.
• "Recursion costs no space." Every active call holds a frame. Depth-n recursion is O(n) space and can exceed a language's stack limit.
• "Two nested loops mean O(n²)." Count total iterations instead. A sliding window whose left index only moves forward is O(n) despite its inner loop.
• "Slicing and string concatenation are free." In most languages a slice copies its elements, and repeatedly concatenating immutable strings can be quadratic.
• "The asymptotically better algorithm is always faster." Asymptotics describe growth. At realistic sizes, constants, allocation and cache behavior can reverse the ranking, which is why measurement still matters.

How to approach it

State the complexity unprompted, once when you propose an approach and again after coding, defining every variable ("n words of maximum length L"). Name the case: worst, expected or amortized. Include auxiliary space and recursion depth, and price every library call you use (sorting, slicing, membership tests on lists). At every level interviewers check the bound of your own code; at mid and senior levels they also ask how it changes when an assumption changes: keys become long strings, inputs become adversarial, or data no longer fits in memory.