How to Analyze Time Complexity (With Examples)
A time complexity cheat sheet for coding interviews: common Big-O patterns, loops, recursion, amortized costs, graphs, space, and how to explain it out loud.
Short answer: to find time complexity in an interview, look at how many times each loop or recursive call runs as the input grows, multiply nested bounds, add sequential steps, and keep only the largest term. One pass is O(n), halving is O(log n), sorting is O(n log n), and full nested scans are O(n²).
This time complexity cheat sheet skips the heavy math. It is the set of rules you can apply while talking, with examples that look like real interview questions.
Big-O in one sentence
Big-O describes how running time grows as the input size n grows. Interviews usually mean the worst case unless someone says average or amortized.
Keep the dominant term and drop constants and smaller terms: O(3n² + 100n) becomes O(n²).
Core patterns
| Pattern | Complexity | Notes |
|---|---|---|
| Single loop over n | O(n) | |
| Two nested loops, each up to n | O(n²) | Three nested: O(n³) |
| Binary search or repeated halving | O(log n) | |
| Comparison-based sort | O(n log n) | |
| Checking all pairs | O(n²) | |
| Generating all subsets | O(2ⁿ) subsets | O(n · 2ⁿ) if you copy each one out |
| Generating all permutations | O(n!) permutations | O(n · n!) if you copy each one out |
Loops with changing bounds
for i in range(n):
for j in range(i, n):
...
The inner loop runs n, then n - 1, and so on down to 1 time. That sums to n(n + 1)/2, which is O(n²). Starting the inner loop at i halves the work but does not change the class.
i = 1
while i < n:
i *= 2
i doubles each time, so the loop runs about log₂ n times: O(log n).
The question to ask each time: does the inner work, summed over every outer iteration, come to n², n log n, or something else?
Recursion and trees
Recursive DFS on a binary tree with n nodes:
- Each node is visited once, so time is O(n).
- Stack space is O(h), where h is the height: O(log n) for a balanced tree, O(n) for a skewed one.
Memoized dynamic programming where each state is computed once:
- Time is number of states × work per state. With O(1) work per state, that is O(states). Coin Change is O(amount × number of coins) for this reason.
Hash maps and sets
On average, insert, lookup and delete are O(1) expected.
In the worst case, heavy collisions can make them O(n). Mention this only if the interviewer asks about implementation details.
Sort, then scan
Sorting followed by a single pass is O(n log n): the sort dominates. Merge Intervals and the two-pointer version of 3Sum follow this shape (3Sum's scan is O(n²), so that dominates there).
Amortized analysis
Dynamic array append: an occasional resize copies everything, but spread across many appends the cost is amortized O(1) per append.
Union-Find: with both path compression and union by rank (or size), each operation costs O(α(n)) amortized, where α is the inverse Ackermann function. In practice you can call it effectively constant. With only one of the two optimisations, the bound is O(log n).
Say "amortized" out loud whenever a single operation's worst case differs from its long-run average.
Graphs
- BFS or DFS with an adjacency list: O(V + E). Number of Islands is O(rows × cols), since every cell is a vertex with at most four edges.
- Dijkstra with a binary heap: O((V + E) log V).
What to say out loud
- "The dominant work is ..."
- "We visit each ... once, so ..."
- "Sorting dominates at O(n log n), then the scan is linear."
Interviewers grade whether you can derive complexity from your own code, not whether you can recite a table. Complexity analysis is part of the technical knowledge score in TechInView's scorecard; how the AI evaluates has the full breakdown.
Common mistakes
- Assuming counting sort everywhere. Counting sort is O(n + k), but it is not comparison-based and only works when keys fall in a small known range k.
- Calling a frequency map O(1) to build. You have to read every element, so building it is O(n).
- Ignoring output size. If you return all subsets, you produce 2ⁿ of them, each up to n long. No algorithm can beat the size of its output.
- Forgetting string costs. Slicing or concatenating strings in a loop often hides an extra factor of n.
Space complexity
Count extra memory: arrays, maps, the recursion stack, and any copies a sort makes.
- In-place sorts use O(1) to O(log n) extra space depending on the algorithm. Python's built-in sort (Timsort) can use O(n).
- A memo table uses O(number of states).
Quick reference
- Single pass: O(n)
- Halve each step: O(log n)
- Nested full scans: O(n²)
- Sort: O(n log n)
- Graph traversal with adjacency list: O(V + E)
- Bitmask DP over subsets: often O(n · 2ⁿ)
To make this automatic, state the complexity out loud after every problem you solve, then check it. The data structure decision guide covers which structure gives which costs, and thinking out loud covers how to fit the explanation into a live round.