Complexity analysis

Problem

Two correct programs can differ by a factor of a million in running time. An interview problem is almost never "can you get the right answer" and almost always "can you get it fast enough, on an input that is too large for the obvious approach". To choose between approaches before you write them, you need a way to compare them that ignores the speed of the machine and the quality of the compiler.

The questions that need this vocabulary look like: find a pair, a window or a path among up to a hundred thousand items; count something over a huge range; or "can you do better than O(n²)?" said out loud by the interviewer. Each constraint on the input size is a hint about which complexity the intended solution has.

Intuition

Count the steps your program takes as a function of the input size n, then keep only the part that dominates once n is large. A loop that visits each item once takes about n steps. Two nested loops take about n × n. A loop that throws away half the remaining items each round takes about log₂ n rounds, because that is how many times you can halve n before nothing is left.

The constants don't matter, because they don't change how the cost grows: doubling n doubles a linear cost, quadruples a quadratic cost, and adds just one step to a logarithmic cost. Those growth rates, not the stopwatch time on your laptop, are what separate an approach that scales from one that never finishes.

Every curve starts near the origin. By n = 16 the quadratic and exponential curves have left the chart while log n has barely moved.

Mechanics

What O(f(n)) means

Say a program takes T(n) steps. We write T(n) = O(f(n)) when, past some input size, T(n) is at most a constant multiple of f(n). Formally: there are constants c and n₀ such that T(n) ≤ c · f(n) for every n ≥ n₀. That is an upper bound. The matching lower bound is Ω, and when both hold the growth is Θ. Interviewers say "big-O" and usually mean the tight Θ for the worst case.

Two consequences give the rules you use daily. Drop constants: 5n + 40 is O(n), since 5n + 40 ≤ 45n for n ≥ 1. Drop lower-order terms: n² + 1,000n is O(n²), because for n ≥ 1,000 the second term is no bigger than the first.

Counting rules

• Sequence: two blocks one after the other add, so keep the larger one.
• Nesting: a loop inside a loop multiplies, but only when the inner count really doesn't depend on the outer variable. A loop over j from i + 1 to n runs 10 times for n = 5, which is n(n−1)/2 and still O(n²).
• Halving: if each round discards a constant fraction of what remains, the round count is logarithmic. Halving 1,024 takes 10 rounds.
• Recursion: multiply the work per call by the number of calls. A function that calls itself twice, each time on n − 1, makes about 2ⁿ calls.
• Library calls have a cost too: x in some_list, s[a:b], sorted(...) and string concatenation inside a loop are each loops in disguise. The Python toolkit page tabulates them.

Best, worst and average case

Linear search finds its target in one step if it is first and n steps if it is last. Unless told otherwise, quote the worst case: it is the guarantee. Average case needs a probability model for the input; quicksort is O(n log n) on average but O(n²) in its worst case, and being able to say both is part of a good answer.

Space complexity

Space counts the extra memory your algorithm allocates beyond the input, including the recursion stack. Making a set of every element is O(n) space; a few integer variables are O(1). A recursive function that goes n levels deep uses O(n) stack space even if it allocates nothing else.

Amortized cost

Some operations are usually cheap and occasionally expensive. Appending to a Python list normally writes one slot, but when the underlying array is full it allocates a bigger one and copies everything. Amortized analysis averages the cost over a whole sequence of operations, not over random inputs: any n appends, starting from an empty list, cost O(n) in total, so each append is O(1) amortized.

Why it works: if the capacity doubles each time it fills, the copies cost 1 + 2 + 4 + … which sums to less than twice the final size. Charge every append a flat 3 units: one pays for its own write and the rest is saved to pay for the next copy. If the array grew by a constant amount instead, the copies would add up to O(n²), and the guarantee would be lost. The same argument explains why a sliding window or monotonic stack that looks like a loop inside a loop is still O(n): each element enters and leaves only once.

Worked example

Trace nine appends to a growable array that starts with room for one element and doubles when full. Each row shows what the append cost (one write plus any copying), the running total, and the average cost per append so far.

Nine appends cost 24 in total, an average of 2.67. The next resize isn't until append 17, so the expensive bars get further apart every time.

Now put the constraint table to work. Suppose a machine does roughly 10⁸ simple steps in the time limit. The largest n each growth rate can handle:

This is why "n up to 10⁵" tells you to aim for O(n log n) or better, and "n up to 20" tells you an exponential search is expected.

Implementation

Complexity is analysed, not implemented, but a habit helps: annotate each line of a solution with what it costs, then multiply or add. Here is the same question, "does any pair sum to the target", at three complexities.

def has_pair_quadratic(nums, target):          # O(n^2) time, O(1) space
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return True
    return False


def has_pair_hash(nums, target):               # O(n) time, O(n) space
    seen = set()
    for x in nums:
        if target - x in seen:                 # set lookup is O(1) on average
            return True
        seen.add(x)
    return False


def has_pair_sorted(nums, target):             # O(n log n) time, O(1) extra space
    nums = sorted(nums)                        # note: sorted() copies, so O(n) space
    left, right = 0, len(nums) - 1
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return True
        if total < target:
            left += 1
        else:
            right -= 1
    return False

Variations and edge cases

• Two inputs, two variables. Looping over a list of length m inside a loop over a list of length n is O(m·n), not O(n²). Name each size separately.
• Hidden loops. result += piece on a string inside a loop can be O(n²) in the worst case; build a list and "".join it once. list.pop(0) and list.insert(0, x) shift every element: use a deque.
• Numbers as input. For an integer n, the "size" of the input is its digit count. A loop to n is exponential in the number of digits, which is why value limits like 10⁹ forbid it.
• Recursion depth. Python's default limit is about a thousand frames. A depth-n recursion on n = 10⁵ crashes, so check the stack space as well as the time.
• Pitfall: the log base. log₂ n and log₁₀ n differ by a constant factor, so the base never appears in big-O.

Complexity and tradeoffs

• Brute force is the baseline. Try everything; it is nearly always correct and usually O(n²), O(n³) or O(2ⁿ). State it first, aloud, and then say which repeated work it does. Every pattern in this reference removes a specific kind of repeated work.
• Time against space. The usual trade is memory for speed: a hash set turns an O(n) membership scan into O(1). The reverse trade exists too, in sorting in place instead of copying, but is rarer in interviews.
• Big-O hides constants. An O(n log n) algorithm with a heavy constant can lose to an O(n²) one for small n. Interview inputs are chosen so that the exponent matters, and the constant rarely does.
• It is an upper bound on growth, not a prediction. Two O(n) solutions can differ by 50× in practice. Use it to rule out approaches, not to rank close ones.
• Where it fails you. It cannot tell you about cache behaviour, input distributions or amortized spikes. Real systems with latency limits care about the worst single operation, not the amortized average.

Problems

Every list problem is taught under one of the pattern pages, so this page has none of its own. Use it as the reading skill behind all of them: for any problem, find the limits, compute the budget, and name the complexity you are aiming for before you code.

No list problem has this page as its home: it teaches the vocabulary every other page uses.

Connections

Complexity analysis is the starting point for every page in this reference. Pages on recursion and the Python toolkit lean on it directly: recursion trees are how you count calls, and the toolkit page gives the cost of each built-in operation. The two-pointer and sliding-window pages are where amortized reasoning pays off.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms (CLRS), chapter 3 (growth of functions) and chapter 16 (amortized analysis).
• Steven Skiena, The Algorithm Design Manual, chapter 2 (algorithm analysis).
• Sedgewick and Wayne, Algorithms, section 1.4 (analysis of algorithms).
• Robert Tarjan, "Amortized Computational Complexity", SIAM Journal on Algebraic and Discrete Methods, 1985.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.