Complexity
Complexity & Big-O
A practical primer for coding interviews: what Big-O means, common bounds, how to analyze loops, and how space complexity fits in.
What Big-O measures
Time complexity describes how the work an algorithm does scales as the input size n grows. In interviews you almost always quote the worst-case Big-O; average case comes up for structures like hash maps.
Big-O drops constant factors and lower-order terms: 3n² + 100n + 5 is O(n²). The goal is a fast answer to “does this approach still work as n grows?”
Common bounds
| Big-O | Name | Typical example | When you see it |
|---|---|---|---|
| O(1) | Constant | Array index, hash map avg get/put | Work independent of input size |
| O(log n) | Logarithmic | Binary search, balanced BST lookup | Halve the search space each step |
| O(n) | Linear | Single pass, scan an array | Touch each element once |
| O(n log n) | Linearithmic | Good sorts (merge/heap), many sort-then-scan | Sorting or divide-and-conquer merge |
| O(n²) | Quadratic | Nested double loop, naive pairs | Every pair / every i,j |
| O(2ⁿ) | Exponential | Full subset enumeration, naive recursion | Include/exclude each element |
| O(n!) | Factorial | All permutations | Orderings (n must be tiny) |
How to count loops
- One loop over
0..n→ usually O(n). - Two nested loops each to
n→ O(n²). - Inner work halves each time (binary-search style) → O(n log n) or O(log n) for a single search.
- Loop plus an O(n) copy/sort inside → multiply: e.g. sort each step → often O(n² log n).
- Early exit does not improve worst-case Big-O; quote the worst path.
Space complexity
How much extra memory beyond the input? Output arrays are sometimes counted separately, clarify in the interview. Recursion depth d usually costs O(d) stack space.
Rough table by structure
| Structure | Access | Search | Insert | Note |
|---|---|---|---|---|
| Array / list | O(1) | O(n) | O(n)* | *Append may be amortized O(1) |
| Hash map / set | - | O(1) avg | O(1) avg | O(n) worst with bad hashing |
| Sorted array | O(1) | O(log n) | O(n) | Binary search enabled |
| Stack / queue | O(1) ends | O(n) | O(1) | End operations only |
| Min/max heap | O(1) min | O(n) | O(log n) | Top-K and priority |
| Balanced BST | - | O(log n) | O(log n) | Ordered traversal |
Work at n = 1000
Logarithms below are base 2, which only changes the constant. At n = 1000, log2(n) is about 10. Naive recursive Fibonacci is Θ(φⁿ), about O(1.618ⁿ). Calling it O(2ⁿ) is a loose upper bound. Quote worst case unless you say average or amortized.
| Big-O | At n = 1000 | Note |
|---|---|---|
| O(1) | 1 | Array index. Hash get/put is average-case, worst-case O(n). |
| O(log n) | ~10 | Binary search, balanced BST. |
| O(n) | 1,000 | One pass. |
| O(n log n) | ~10,000 | Mergesort, heapsort, Timsort. |
| O(n²) | 1,000,000 | Two nested passes. |
| O(n³) | 1,000,000,000 | Floyd–Warshall, three nested passes. |
| O(2ⁿ) | 2^1000 | Subset include/exclude. Materializing each subset is Θ(n · 2ⁿ). |
| O(n!) | 1000! | All permutations. |
Algebra
- Drop constants:
O(2n)isO(n). - Drop lower terms:
O(n² + n)isO(n²). - Different inputs stay different: a loop over
athen a loop overbisO(a + b). - Nested work multiplies:
O(n)outside anO(m)body isO(n · m). - Sequential work adds:
O(n)thenO(m)isO(n + m).
Early exit can improve the best case. Worst-case Big-O stays the worst path.
Where extra space comes from
Auxiliary space excludes the input. Say so when you quote it. Output storage is sometimes counted separately. Ask which one the interviewer wants. In-place means O(1) extra space. The input itself still occupies O(n).
| Source | Extra space |
|---|---|
| A fixed set of scalars | O(1) |
| A string or array of length n | O(n) |
| Recursion | O(depth) stack frames |
| Recursive binary search | O(log n) stack. The loop form is O(1). |
| Hash map of the input | O(n) |
Amortized costs
α(n) is the inverse Ackermann function. For every structure you will see in an interview it is at most 4. A hash table with a forced collision chain is O(n) per call and stays there. Amortized O(1) assumes a working hash.
| Operation | Worst one call | Amortized | Condition |
|---|---|---|---|
| Dynamic array append | O(n) | O(1) | Geometric resize |
| Hash table insert | O(n) | O(1) | Evenly spread hash, plus resize |
| Union-find | O(n) | O(α(n)) | Union by rank or size, and path compression |
| Splay tree | O(n) | O(log n) | Amortized over a sequence of ops |
Distinctions the structure table does not spell out
The live table already lists array, hash map, sorted array, stack/queue, heap, and balanced BST. These rows add the missing operations.
| Structure | Operation | Time | Note |
|---|---|---|---|
| Array | Insert or delete in the middle | O(n) | Elements shift |
| Singly linked list | Insert or delete at the head | O(1) | |
| Singly linked list | Insert after a node you hold | O(1) | Finding the node is a separate O(n) |
| Singly linked list | Delete a node you hold | O(n) | You need the previous node, unless you copy the successor and are not at the tail |
| Doubly linked list | Delete a node you hold | O(1) | |
| Heap | Build from n items | O(n) | Floyd's bottom-up build, not n pushes |
Sorting
Stable means equal keys keep their original order.
| Algorithm | Best | Average | Worst | Extra space | Stable | Note |
|---|---|---|---|---|---|---|
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | What Python actually runs |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | Best case is nearly sorted input |
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes | O(n) best case needs a swapped-flag exit |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No | |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) avg | No | Worst-case recursion depth is O(n), so extra space is O(n) |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | k is the key range. Integer keys |
| Radix (LSD) | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | Yes | d digits, b base |
| Bucket | O(n + k) | O(n + k) | O(n²) | O(n) | If the inner sort is stable | Average assumes a uniform spread |
Graphs
Times assume an adjacency list. An adjacency matrix makes DFS and BFS O(V²). Dijkstra with a Fibonacci heap is O(E + V log V). Interviews expect the binary-heap bound. A topological sort of a graph that contains a cycle does not produce a valid order. Kahn's algorithm reports that by leaving nodes with remaining indegree.
| Algorithm | Time | Extra space | Requires | Pattern |
|---|---|---|---|---|
| DFS | O(V + E) | O(V) | graph-dfs | |
| BFS | O(V + E) | O(V) | Shortest path in hops, unweighted | grid-graph-bfs |
| Dijkstra | O((V + E) log V) | O(V) | Non-negative weights. Bound is a binary heap | shortest-path-weighted |
| Bellman–Ford | O(VE) | O(V) | Negative weights allowed. One more pass after V − 1 rounds detects a negative cycle | shortest-path-weighted |
| Floyd–Warshall | O(V³) | O(V²) | All pairs. Negative edges allowed. dist[i][i] < 0 means a negative cycle | — |
| Topological sort | O(V + E) | O(V) | Directed acyclic graph | topological-sort |
| Kruskal | O(E log E) | O(V) | Undirected. Sort edges, then union-find | minimum-spanning-tree |
| Prim | O(E log V) | O(V) | Undirected and connected. Bound is a binary heap. Dense + array is O(V²) | minimum-spanning-tree |
Interview tips
- Always state time and space together; call out trade-offs (e.g. O(n) time / O(n) map vs O(n²) / O(1)).
- Use “amortized” and “average” carefully, correct for dynamic arrays and hash tables.
- Pattern choice often sets the bound: sliding window O(n), naive subarrays O(n²).
- Every approach on this site shows complexity badges, learn the template, then defend the Big-O in your own words.
Next step
Move into foundations on the roadmap, browse patterns, or open resources for platforms, books, and references, or the language cards: Python, TypeScript, C#.
For a visual take on these bounds, see math foundations - growth rates, logarithms, and summations.