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 |
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.