Time and Space Complexity Analysis

Almost every interview solution ends with the same follow-up: "What are the time and space complexities?" This article shows how to answer quickly and correctly, including amortized analysis and the usual ways to save memory.

Intuition

Complexity describes how the cost of an algorithm grows with the input size, not how many milliseconds it takes on one machine. Count basic operations (arithmetic, comparisons, reading or writing a variable), keep only the fastest-growing term, and drop constant factors.

• O(g(n)) is an upper bound: for large n the cost is at most c * g(n).
• Ω(g(n)) is a lower bound, and Θ(g(n)) means both bounds hold.
• Worst case, average (expected) case and amortized cost answer different questions. "Quicksort is O(n log n)" is only true on average; its worst case is O(n^2).

Two rules handle most code:

• Sequential blocks add, and the largest term wins: O(n) + O(n log n) = O(n log n).
• Nested loops multiply: a loop over n items containing a loop over m items costs O(n * m).

Anything not tied to the input size is a constant. A loop that always runs 26 times (once per letter) is O(1), which is why a letter-frequency array uses O(1) space.

When to use it in interviews / OAs

• State time and space at the end of every solution and name the variables: "O(n log n) time for n intervals, O(n) extra space."
• Read the constraints before coding and infer the intended complexity. A rough budget is 10^8 simple operations per second in C++ or Java and about 10^7 in Python.

Input size n	Typical target	Typical technique
n ≤ 10	O(n!)	permutations, backtracking
n ≤ 20	O(2^n * n)	subsets, bitmask DP
n ≤ 40	O(2^(n/2))	meet in the middle
n ≤ 500	O(n^3)	interval DP, Floyd-Warshall
n ≤ 5,000	O(n^2)	2D DP, all pairs
n ≤ 10^6	O(n log n) or O(n)	sorting, heaps, binary search, two pointers
n up to 10^18	O(log n) or O(sqrt(n))	binary search on the answer, math

• When the interviewer asks "can you do better?", the table tells you what better means. From O(n^2) the next step is usually O(n log n) (sorting, a heap, binary search) or O(n) (hash map, two pointers, monotonic stack).

Template: analyzing code quickly

Loops

Count how many times the innermost statement runs, and watch loops whose bounds shrink or jump:

• i doubles each step (i *= 2): O(log n) iterations.
• The inner loop runs j from i to n: n + (n - 1) + ... + 1 = O(n^2).
• The inner loop is for j in range(i, n, i): n/1 + n/2 + n/3 + ... is the harmonic series, O(n log n) in total.

Recursion

Write the recurrence, then recognize it:

Recurrence	Result	Example
T(n) = T(n/2) + O(1)	O(log n)	binary search
T(n) = T(n/2) + O(n)	O(n)	quickselect, average case
T(n) = 2T(n/2) + O(1)	O(n)	traversing a balanced tree
T(n) = 2T(n/2) + O(n)	O(n log n)	merge sort
T(n) = T(n - 1) + O(n)	O(n^2)	quicksort with bad pivots
T(n) = 2T(n - 1) + O(1)	O(2^n)	Tower of Hanoi, include/exclude recursion

For divide and conquer the general tool is the master theorem. For T(n) = a * T(n/b) + f(n), compare the work at the root, f(n), with the total work at the leaves, n^(log_b a):

1. f(n) is polynomially smaller: the leaves dominate and T(n) = Θ(n^(log_b a)).
2. They match: every level costs the same and T(n) = Θ(n^(log_b a) * log n). More generally, if f(n) = Θ(n^(log_b a) * log^k n), then T(n) = Θ(n^(log_b a) * log^(k+1) n).
3. f(n) is polynomially larger (and a * f(n/b) ≤ c * f(n) for some constant c < 1): the root dominates and T(n) = Θ(f(n)).

For recursion that is not divide and conquer, use: total cost = number of calls × work per call. Backtracking over all subsets makes about 2^n calls and copies up to n elements at each leaf, so it is O(n * 2^n).

Amortized analysis

Some operations are occasionally expensive but cheap over any sequence of operations. Amortized cost is a worst-case guarantee for the whole sequence; it involves no probability.

The classic example is appending to a dynamic array (Python list, C++ vector, Java ArrayList). When the array is full, it doubles its capacity and copies every element. One append can cost O(n), but copies happen only at sizes 1, 2, 4, 8, ..., so n appends copy fewer than 2n elements in total:

def total_copies(n: int) -> int:
    """Element copies done by a capacity-doubling array during n appends."""
    cap, size, copies = 1, 0, 0
    for _ in range(n):
        if size == cap:  # full: allocate twice the space and copy everything
            copies += size
            cap *= 2
        size += 1
    return copies

Because total_copies(n) < 2n, each append is amortized O(1). There are three standard ways to argue this, and an interviewer may ask you to name one:

• Aggregate method: total cost of n operations divided by n.
• Accounting method: charge every append 3 units. One pays for the write; two are saved to pay for copying this element and one older element at the next resize.
• Potential method: define Φ = 2 * size - capacity. Amortized cost = actual cost + change in Φ, which is exactly 3 for every append, with or without a resize.

The same "each element is added once and removed at most once" argument explains most O(n) interview solutions that contain a nested while loop:

def next_greater(nums: list[int]) -> list[int]:
    """For each position, the first larger value to its right, or -1."""
    ans = [-1] * len(nums)
    stack: list[int] = []  # indices still waiting for an answer
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:  # each index is popped at most once
            ans[stack.pop()] = x
        stack.append(i)
    return ans

The inner loop may pop many indices in one iteration, but every index is pushed once and popped at most once, so the total work is O(n). Sliding windows (both pointers only move forward) and union-find with path compression are analyzed the same way.

Space complexity and saving memory

Space complexity measures the extra memory used as the input grows. Say whether you count the input and the output; most interviewers mean auxiliary space. Remember the hidden costs:

• Recursion uses stack space proportional to its maximum depth: O(h) for a tree of height h, which becomes O(n) for a skewed tree. Python's default recursion limit is about 1000 frames.
• Slicing (a[i:j]), sorted(), string concatenation and converting to a set or dict all allocate new memory.

Common ways to reduce memory:

• Rolling arrays. If row i of a DP table only reads row i - 1, keep one or two rows. In 0/1 knapsack, iterate the capacity downward so the single row still holds the previous item's values when you read it:

def knapsack_01(weights: list[int], values: list[int], cap: int) -> int:
    dp = [0] * (cap + 1)  # dp[c] = best value using capacity c
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):  # downward, so each item is used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]

• Store only what you need: adjacency lists instead of an adjacency matrix for sparse graphs (O(V + E) instead of O(V^2)), indices instead of copied subarrays, counts instead of the elements themselves.
• Pack booleans: a bitset, or a Python int used as a bit mask, stores each flag in one bit instead of a byte or a whole object.
• Reuse the input when allowed: mark visited cells directly in the grid, or hide extra information in a value you already store. Union-find, for example, can keep parents and set sizes in a single array by storing -size at each root.
• Know the floor: storing an arbitrary integer from 1 to n takes at least log2(n) bits, so no trick can store less than the information the answer contains.

Python built-ins cheat sheet

Operation	Cost
list.append, list.pop()	O(1) amortized
list.pop(0), list.insert(0, x), x in some_list	O(n)
dict / set lookup, insert, delete	O(1) average, O(n) worst case
collections.deque append or pop at either end	O(1)
heapq.heappush, heapq.heappop	O(log n)
heapq.heapify	O(n)
sorted, list.sort	O(n log n)
slicing a[i:j], string s + t	O(length of the result)

Complexity

Analysis itself has no runtime, but the examples above are useful reference points: total_copies shows O(1) amortized appends, next_greater runs in O(n) time and O(n) space, and knapsack_01 runs in O(n * cap) time with O(cap) space instead of O(n * cap).

Common pitfalls

• Hidden loops: x in some_list inside a loop turns O(n) into O(n^2). Repeated s += ch on strings can also be quadratic; collect pieces in a list and "".join them.
• Mixing up variables: a grid is O(rows * cols), not O(n^2), and a graph is O(V + E). Always name what n means.
• Calling hash map operations O(1) worst case. They are O(1) on average; adversarial keys can degrade them.
• Claiming quicksort is O(n log n) in the worst case. Say "O(n log n) expected, O(n^2) worst case".
• Forgetting recursion depth in space, or forgetting the output size. Listing all permutations costs at least O(n * n!) because that is the size of the output.
• Treating amortized O(1) as worst-case O(1). A single append can still take O(n), which matters in latency-sensitive design discussions.

Interview variations

• "Your solution is O(n^2). Can you do O(n log n)?" Look for sorting plus binary search, a heap, or divide and conquer.
• "Can you do it with O(1) extra space?" Think two pointers, in-place swaps, reusing the input, or bit tricks.
• "What if the data does not fit in memory?" Use a single streaming pass, external merge sort, or sampling.
• "Analyze this recursive function." Write the recurrence and match it against the table or the master theorem.
• "Is there a polynomial algorithm?" If the problem resembles a known NP-hard problem (traveling salesman, graph coloring, subset sum with huge values), no polynomial algorithm is known; expect small constraints and an exponential search or a DP over subsets.