Big-O for Interviews
Use Big-O the way interviewers do: pick an algorithm from the input constraints, avoid hidden linear-time built-ins, and state the time and space complexity of loops, two-pointer scans and recursion without hesitating.
🎯 What you'll learn
- Turning input constraints into a target complexity
- Costs of built-in operations in Python, JavaScript and C#
- Amortized cost and why two pointers are O(n)
- Analysing recursion and space complexity
📚 Before you start
In an interview you need Big-O for two things: choosing an algorithm before you write it (will O(n²) pass for this input size?) and stating the complexity of what you wrote without hesitation. This topic is the practical subset: the costs of built-in operations in Python, JavaScript and C#, the input-size table, amortized cost, and how to analyse recursion. For the fundamentals of the notation itself, see languages/javascript/24-time_and_space_complexity.
1From Constraints to Complexity
Interview problems often state constraints like 1 ≤ n ≤ 10^5. A typical machine does roughly 10^8 simple operations per second, so the constraint tells you which complexity the interviewer expects:
| Input size n | Acceptable complexity | Typical techniques |
|---|---|---|
| ≤ 10 | O(n!) , O(2ⁿ·n) | permutations, brute-force backtracking |
| ≤ 20–25 | O(2ⁿ) | subsets, bitmask DP |
| ≤ 500 | O(n³) | triple loops, Floyd–Warshall, interval DP |
| ≤ 5,000 | O(n²) | 2D DP, all pairs |
| ≤ 10^5 – 10^6 | O(n log n) or O(n) | sorting, heaps, two pointers, hashing |
| ≥ 10^8 | O(log n) or O(1) | binary search, math |
If no constraint is given, ask: "How large can the input get?" The answer often tells you whether the brute force is acceptable.
2Costs of Built-in Operations
Knowing these prevents hidden O(n²) solutions, such as calling list.pop(0) or Array.shift() inside a loop.
| Operation | Python | JavaScript | C# | Cost |
|---|---|---|---|---|
| index read/write | a[i] | a[i] | a[i], list[i] | O(1) |
| append at end | a.append(x) | a.push(x) | list.Add(x) | O(1) amortized |
| remove from end | a.pop() | a.pop() | list.RemoveAt(list.Count-1) | O(1) |
| insert/remove at front | a.insert(0,x), a.pop(0) | a.unshift(x), a.shift() | list.Insert(0,x), RemoveAt(0) | O(n) |
| deque at both ends | collections.deque | (no built-in; use index pointers) | LinkedList<T>, or Queue<T> for FIFO | O(1) |
| membership in list | x in a | a.includes(x) | list.Contains(x) | O(n) |
| hash map get/set | d[k] | map.get(k) | dict[k], TryGetValue | O(1) average |
| hash set add/has | s.add(x), x in s | set.add/has | HashSet<T>.Add/Contains | O(1) average |
| sort | sorted(a), a.sort() | a.sort((x,y)=>x-y) | Array.Sort, list.Sort() | O(n log n) |
| slice / copy | a[i:j] | a.slice(i,j) | list.GetRange(i,n) | O(j−i) |
| string concatenation in a loop | s += c | s += c | s += c | O(n²) total; use "".join / array join / StringBuilder |
| heap push/pop | heapq.heappush/heappop | (no built-in; implement or use a library) | PriorityQueue<T,P> | O(log n) |
| sorted map | (no built-in; bisect on a list, or sortedcontainers) | (none) | SortedDictionary, SortedSet | O(log n) |
JavaScript's default
sort()compares elements as strings:[10, 9, 1].sort()gives[1, 10, 9]. Always pass a comparator for numbers.
3Amortized Cost
A dynamic array (Python list, JS array, C# List<T>) doubles its capacity when full. One append occasionally costs O(n) for the copy, but n appends cost O(n) in total, so each append is O(1) amortized. The same reasoning applies to hash tables that resize, and to the two-stack queue (each element is moved at most once).
In an interview, say "amortized O(1)" rather than just "O(1)" when it applies. It shows you know why.
4Analysing Loops
- Sequential loops add: O(n) + O(m) = O(n + m).
- Nested loops multiply: for each of n items, an inner O(m) loop → O(n·m).
- Halving loops are logarithmic:
while n > 0: n //= 2runs O(log n) times. - Two pointers that only move forward are O(n) even though there are two loops: each pointer moves at most n times in total. This is the most common place candidates over-count.
# Sliding window: looks nested, is O(n)
left = 0
for right in range(len(a)): # right moves n times in total
while window_invalid():
left += 1 # left also moves at most n times in total5Analysing Recursion
Count (number of calls) × (work per call), or use the shape of the recursion tree:
| Recursion | Calls | Work per call | Total |
|---|---|---|---|
binary search: f(n/2) | log n | O(1) | O(log n) |
| tree traversal: visit each node once | n | O(1) | O(n) |
merge sort: 2·f(n/2) + O(n) merge | log n levels | O(n) per level | O(n log n) |
naive Fibonacci: f(n-1) + f(n-2) | ~2ⁿ | O(1) | O(2ⁿ) |
| memoized Fibonacci | n distinct states | O(1) | O(n) |
| subsets: include/exclude each element | 2ⁿ leaves | O(n) to copy | O(n·2ⁿ) |
| permutations | n! leaves | O(n) to copy | O(n·n!) |
Space of recursion is the maximum depth of the call stack: O(log n) for balanced divide and conquer, O(n) for a linked-list-shaped tree or naive DFS on a path. Python's default recursion limit is about 1,000 frames, so deep recursion on large inputs needs an iterative version or sys.setrecursionlimit.
6Space Complexity Conventions
- Output space (the array you must return) is usually not counted, but say so: "O(1) extra space, not counting the output".
- Input modification: an in-place algorithm that sorts the input uses O(1) extra space, but mutates the caller's data; mention the trade-off.
- Sorting itself uses memory: Python's Timsort uses O(n) auxiliary space; C#'s
Array.Sort(introsort) uses O(log n) stack.
⚠️ Common Pitfalls
- Hidden linear operations inside loops:
x in list,list.pop(0),arr.shift(),string +=, slicing. - Counting a sliding window as O(n²) because it has a nested
while. - Forgetting the cost of sorting when the rest of the algorithm is O(n): the total is O(n log n).
- Ignoring recursion stack space.
- Saying O(1) for hash maps without "average": worst case is O(n) with many collisions.
- Using
nfor two different inputs: use n and m (e.g. O(n + m) for two strings).
📋 Quick Reference
10^8 ops/sec n≤20: 2^n · n≤500: n^3 · n≤5k: n^2 · n≤10^6: n log n / n
Hidden O(n): x in list · pop(0)/shift · insert(0) · slicing · string +=
Amortized O(1): append/push/Add, hash insert, two-stack queue
Recursion: calls × work per call; space = max depth🧠 Key takeaways
- About 10⁸ operations per second: use the constraint table to choose the target complexity.
- Watch for hidden O(n) built-ins in loops: list membership,
pop(0)/shift, slicing, string+=. - Appends and hash inserts are amortized O(1); forward-only two pointers are O(n).
- Recursion = calls × work per call; space = max stack depth.
🛠️ Practice exercises
Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.
✅ Check yourself
Answer the questions — feedback is instant.