Chapter Goal: Develop the ability to instantly read any piece of code and state its time and space complexity — correctly and confidently. Every algorithm and data structure in this guide is analyzed using exactly the framework taught here. Interviewers will ask "what is the complexity?" after every solution you write. Master this chapter so that question never trips you up.
Complexity notation describes how an algorithm's resource usage scales as
the input size n grows. We always describe the dominant behavior for
large n, ignoring constants and lower-order terms.
f(n) = O(g(n)) means: f grows no faster than g.
More precisely: there exist constants c > 0 and n₀ such that
f(n) ≤ c · g(n) for all n ≥ n₀.
This is the notation interviews use almost exclusively — it gives you a guarantee that the algorithm won't be worse than a certain bound.
f(n) = 3n² + 5n + 2
= O(n²) ← Drop constants & lower-order terms
f(n) = 7 = O(1) (constant)
f(n) = 4n + 100 = O(n) (linear)
f(n) = 2n² + 3n + 1 = O(n²) (quadratic)
f(n) = n log n + n = O(n log n)(linearithmic)
Dropping rules (both are legal and standard):
f(n) = Ω(g(n)) means: f grows at least as fast as g.
Used when making provable lower-bound claims about problem difficulty.
Example: Any comparison-based sort requires Ω(n log n) comparisons.
No matter how clever your algorithm, you cannot do better.
f(n) = Θ(g(n)) means: f grows at exactly the same rate as g.
Formally: f(n) = O(g(n)) AND f(n) = Ω(g(n)).
Merge sort is Θ(n log n) — it is always n log n, in every case.
Bubble sort is Θ(n²) in the worst case, Θ(n) in the best case.
Interview reality check: When an interviewer (or you) says "this is O(n²)", they almost always mean Θ(n²) — the tight bound. Big O is used loosely. Technically, bubble sort is also O(n³), O(n⁴), O(2ⁿ) — all are valid upper bounds. But we always give the tightest useful upper bound.
n = 1,000
O(1) → 1 operation
O(log n) → 10 operations
O(√n) → 31 operations
O(n) → 1,000 operations
O(n log n) → 10,000 operations
O(n²) → 1,000,000 operations ← Interview danger zone
O(n³) → 10⁹ operations ← Usually too slow
O(2ⁿ) → 10³⁰¹ operations ← Only viable for n ≤ 20
O(n!) → 10²⁵⁶⁷ operations ← Only viable for n ≤ 11
Any constant multiplier is absorbed into Big O.
// O(3n) = O(n)
for (int i = 0; i < 3 * n; i++) doWork();
// O(n/2) = O(n)
for (int i = 0; i < n; i += 2) doWork();Keep only the fastest-growing term.
// O(n² + n) = O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) doWork(); // n² work
for (int i = 0; i < n; i++) doWork(); // n work
// Total: n² + n → dominated by n²
// O(n + log n) = O(n)
// O(n² + 2ⁿ) = O(2ⁿ)
// O(n! + n²) = O(n!)// O(n) + O(n) = O(n) — not O(2n)
for (int i = 0; i < n; i++) doA(); // O(n)
for (int i = 0; i < n; i++) doB(); // O(n)
// Total: O(n)
// O(n) + O(m) = O(n + m) — different input sizes stay separate
for (int x : arrA) doA(); // O(n)
for (int x : arrB) doB(); // O(m)
// Total: O(n + m)// O(n) × O(n) = O(n²)
for (int i = 0; i < n; i++) // Outer: n iterations
for (int j = 0; j < n; j++) // Inner: n iterations each
doWork(); // Total: n²
// O(n) × O(m) = O(n·m)
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
doWork();
// O(n) × O(log n) = O(n log n)
for (int i = 0; i < n; i++) // Outer: n iterations
binarySearch(arr, n, target); // Inner: O(log n) each// ── PATTERN 1: Linear loop ──────────────────────────── O(n)
for (int i = 0; i < n; i++) { ... }
// ── PATTERN 2: Loop stepping by k ───────────────────── O(n/k) = O(n)
for (int i = 0; i < n; i += 2) { ... } // Still O(n)
// ── PATTERN 3: Loop halving ──────────────────────────── O(log n)
for (int i = 1; i < n; i *= 2) { ... } // i = 1,2,4,8,...
for (int i = n; i > 0; i /= 2) { ... } // i = n,n/2,n/4,...
// ── PATTERN 4: Nested linear loops ──────────────────── O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) { ... }
// ── PATTERN 5: Nested, inner depends on outer ────────── O(n²)
for (int i = 0; i < n; i++)
for (int j = 0; j < i; j++) { ... } // 0+1+2+...+(n-1) = n(n-1)/2 = O(n²)
// ── PATTERN 6: Nested, inner is constant-bounded ─────── O(n)
for (int i = 0; i < n; i++)
for (int j = 0; j < 10; j++) { ... } // Inner: always 10 → O(10n) = O(n)
// ── PATTERN 7: Outer linear, inner halving ───────────── O(n log n)
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j *= 2) { ... }
// ── PATTERN 8: Three nested linear loops ─────────────── O(n³)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++) { ... }
// ── PATTERN 9: Branching loops with early exit ──────────O(n) worst
for (int i = 0; i < n; i++) {
if (arr[i] == target) return i; // May exit early, but O(n) worst case
}Use this during interviews when you need to estimate whether your solution will pass given the constraints.
| Input Size (n) | Max Acceptable Complexity | Typical Algorithm |
|---|---|---|
| n ≤ 10 | O(n!) | Brute force permutations |
| n ≤ 20–25 | O(2ⁿ) | Subset enumeration, bitmask DP |
| n ≤ 100 | O(n³) | Floyd-Warshall, 3-nested loops |
| n ≤ 1,000 | O(n²) | Bubble/Insertion sort, O(n²) DP |
| n ≤ 10⁵ | O(n log n) | Merge sort, heap ops, BST ops |
| n ≤ 10⁶ | O(n) | Linear scan, hash map, BFS/DFS |
| n ≤ 10⁸ | O(log n) or O(1) | Binary search, math formulas |
Interview Trick: Assume ~10⁸ operations per second on modern hardware. So if n = 10⁵ and your algorithm is O(n²): 10¹⁰ operations → TLE (too slow). If your algorithm is O(n log n): 10⁵ × 17 ≈ 1.7×10⁶ operations → fast enough.
Space complexity measures how much extra memory an algorithm uses, as a function of the input size.
Input Space: Memory occupied by the input itself. Usually not counted unless the problem explicitly asks for "in-place."
Auxiliary Space: Extra memory used by the algorithm beyond the input. This is what "space complexity" usually means in interviews.
// --- O(1) auxiliary space (in-place) ---
void reverseArray(vector<int>& arr) {
int l = 0, r = arr.size() - 1;
while (l < r) swap(arr[l++], arr[r--]);
// Only uses 2 extra variables regardless of n
}
// --- O(n) auxiliary space ---
vector<int> copyArray(const vector<int>& arr) {
vector<int> result(arr); // Creates a new array of size n
return result;
}
// --- O(n) auxiliary space from hash map ---
bool hasDuplicate(const vector<int>& arr) {
unordered_set<int> seen; // Grows with n
for (int x : arr) {
if (seen.count(x)) return true;
seen.insert(x);
}
return false;
}
// --- O(n²) auxiliary space ---
vector<vector<int>> buildMatrix(int n) {
return vector<vector<int>>(n, vector<int>(n, 0)); // n² cells
}Every recursive call adds a stack frame. The depth of recursion equals the space used.
// --- O(n) recursive space ---
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // n frames on the stack
}
// Call stack for factorial(5):
// factorial(5) → factorial(4) → factorial(3) → factorial(2) → factorial(1)
// | | | | return 1
// | | | return 2
// | | return 6
// | return 24
// return 120
// Peak stack depth = n frames = O(n) space
// --- O(log n) recursive space ---
int binarySearch(vector<int>& arr, int l, int r, int target) {
if (l > r) return -1;
int mid = l + (r - l) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) return binarySearch(arr, mid+1, r, target);
return binarySearch(arr, l, mid-1, target);
// Each call halves the range → O(log n) depth
}
// --- O(n) recursive space for tree DFS ---
void dfs(TreeNode* node) {
if (!node) return;
dfs(node->left);
dfs(node->right);
// Depth of recursion = height of tree = O(n) in worst case (skewed tree)
// = O(log n) in balanced tree
}| Algorithm / Pattern | Time | Space |
|---|---|---|
| Iterative loop | O(n) | O(1) |
| Recursive depth-n | O(n) | O(n) |
| Recursive depth-log n | O(log n) | O(log n) |
| Merge sort | O(n log n) | O(n) |
| Quick sort (avg) | O(n log n) | O(log n) |
| BFS | O(V + E) | O(V) |
| DFS | O(V + E) | O(V) |
| Memoized recursion (n states) | O(n) | O(n) |
| 2D DP (n×m) | O(n·m) | O(n·m) |
| 2D DP optimized (rolling array) | O(n·m) | O(m) |
Amortized analysis gives the average cost per operation over a sequence of operations, even when individual operations have wildly different costs.
vector::push_backMost push_back calls are O(1). But occasionally the vector must resize,
which copies all elements — that one call is O(n). So is push_back O(1) or O(n)?
The answer: O(1) amortized — and here is why.
Starting capacity: 1. Each resize doubles capacity.
Push 1: size=1, cap=1 → no resize needed
Push 2: size=2, cap=2 → resize! copy 1 element (cap becomes 2)
Push 3: size=3, cap=4 → resize! copy 2 elements (cap becomes 4)
Push 4: size=4, cap=4 → no resize
Push 5: size=5, cap=8 → resize! copy 4 elements (cap becomes 8)
Push 6: size=6, cap=8 → no resize
Push 7: size=7, cap=8 → no resize
Push 8: size=8, cap=8 → no resize
Push 9: size=9, cap=16 → resize! copy 8 elements
Total copies after n pushes: 1 + 2 + 4 + 8 + ... ≤ 2n
Average cost per push: 2n / n = O(1) ✅
Each element is moved at most twice across all resize operations. So n pushes cost at most 3n work total — O(1) per push, amortized.
// --- Union-Find with path compression ---
// Individual find() can be O(n) worst case
// But over m operations on n elements: O(m · α(n)) amortized
// where α is the inverse Ackermann function — practically O(1)
// --- Hash map insertions ---
// Usually O(1), but rehashing is O(n)
// Over n insertions: O(1) amortized per insertion
// --- Stack operations for Monotonic Stack ---
// Each element is pushed once and popped once
// Total work over all iterations: O(n)
// Amortized cost per element: O(1)
// Example: Next Greater Element
vector<int> nextGreater(vector<int>& nums) {
int n = nums.size();
vector<int> result(n, -1);
stack<int> st; // indices
for (int i = 0; i < n; i++) {
// Each element pushed and popped at most ONCE
// Total loop body executes O(n) times despite the inner while
while (!st.empty() && nums[st.top()] < nums[i]) {
result[st.top()] = nums[i];
st.pop();
}
st.push(i);
}
return result;
// Time: O(n) total — O(1) amortized per element
}A recurrence relation expresses the time complexity T(n) of a recursive function in terms of T on a smaller input.
The template:
T(n) = [number of subproblems] × T([subproblem size]) + [work done at this level]
// Factorial: one subproblem of size n-1, O(1) work per call
// T(n) = T(n-1) + O(1)
// Binary search: one subproblem of size n/2, O(1) work per call
// T(n) = T(n/2) + O(1)
// Merge sort: two subproblems of size n/2, O(n) work to merge
// T(n) = 2T(n/2) + O(n)
// Naive Fibonacci: two subproblems of size n-1 and n-2
// T(n) = T(n-1) + T(n-2) + O(1)Example: T(n) = T(n-1) + O(1)
T(n) = T(n-1) + 1
= T(n-2) + 1 + 1
= T(n-3) + 1 + 1 + 1
= T(n-k) + k
At k = n-1: T(1) + (n-1) = O(n)
Example: T(n) = T(n/2) + O(1) (Binary Search)
T(n) = T(n/2) + 1
= T(n/4) + 1 + 1
= T(n/8) + 1 + 1 + 1
After k steps: T(n/2^k) + k
When n/2^k = 1: k = log₂(n)
T(n) = O(log n)
Example: T(n) = 2T(n/2) + O(n) (Merge Sort)
Level 0: 2⁰ × T(n/2⁰) → n work
Level 1: 2¹ × T(n/2¹) → n work (2 subproblems × n/2 each)
Level 2: 2² × T(n/2²) → n work (4 subproblems × n/4 each)
...
Level k: 2^k × T(n/2^k) → n work
Total levels = log₂(n)
Total work = n × log₂(n) = O(n log n)
The Master Theorem solves recurrences of the form:
T(n) = a × T(n/b) + O(n^d)
a = number of subproblems
b = factor by which input shrinks
d = exponent of work done outside the recursive calls
Three cases:
| Condition | Solution | Intuition |
|---|---|---|
| d > log_b(a) | O(n^d) | Work at top level dominates |
| d = log_b(a) | O(n^d · log n) | Work balanced across all levels |
| d < log_b(a) | O(n^(log_b a)) | Work at leaf level dominates |
Common Applications:
| Recurrence | a | b | d | Case | Solution |
|---|---|---|---|---|---|
| Binary Search: T(n/2) + 1 | 1 | 2 | 0 | d = log₂1 = 0 → Case 2 | O(log n) |
| Merge Sort: 2T(n/2) + n | 2 | 2 | 1 | d = log₂2 = 1 → Case 2 | O(n log n) |
| Quick Sort (avg): 2T(n/2) + n | 2 | 2 | 1 | Same as merge sort | O(n log n) |
| Strassen: 7T(n/2) + n² | 7 | 2 | 2 | d=2 < log₂7≈2.81 → Case 3 | O(n^2.81) |
| Linear: T(n/2) + n | 1 | 2 | 1 | d=1 > log₂1=0 → Case 1 | O(n) |
T(n) = T(n-1) + O(1) → O(n) Linear recursion (factorial)
T(n) = T(n-1) + O(n) → O(n²) Insertion sort recursively
T(n) = T(n/2) + O(1) → O(log n) Binary search
T(n) = T(n/2) + O(n) → O(n) Quickselect (average)
T(n) = 2T(n-1) + O(1) → O(2ⁿ) Tower of Hanoi, naive subsets
T(n) = 2T(n/2) + O(1) → O(n) Tree traversal
T(n) = 2T(n/2) + O(n) → O(n log n) Merge sort
T(n) = 2T(n/2) + O(n²) → O(n²) (work dominates)
T(n) = T(n-1) + T(n-2)→ O(2ⁿ) Naive Fibonacci
For T(n) = 2T(n/2) + n (Merge Sort):
Level 0: [n] work: n
/ \
Level 1: [n/2] [n/2] work: n/2 + n/2 = n
/ \ / \
Level 2: [n/4][n/4] [n/4][n/4] work: 4 × n/4 = n
...
Level log(n): [1][1][1]...[1] work: n × 1 = n
Total levels: log n
Work per level: n
Total: n × log n = O(n log n)
| Container | Operation | Time Complexity | Notes |
|---|---|---|---|
vector |
operator[], at() |
O(1) | Random access |
vector |
push_back, emplace_back |
O(1) amortized | Occasional O(n) resize |
vector |
pop_back |
O(1) | |
vector |
insert (middle) |
O(n) | Shifts elements |
vector |
erase (middle) |
O(n) | Shifts elements |
vector |
front, back |
O(1) | |
vector |
size, empty |
O(1) | |
vector |
reserve(n) |
O(n) | One-time cost |
vector |
clear |
O(n) | Destroys elements |
vector |
find (linear) |
O(n) | No built-in |
deque |
push_front, push_back |
O(1) amortized | |
deque |
pop_front, pop_back |
O(1) | |
deque |
operator[] |
O(1) | Slightly slower than vector |
list |
push_front, push_back |
O(1) | |
list |
insert (given iterator) |
O(1) | |
list |
erase (given iterator) |
O(1) | |
list |
find |
O(n) | No random access |
| Container | Operation | Time Complexity |
|---|---|---|
map / set |
find |
O(log n) |
map / set |
insert, emplace |
O(log n) |
map / set |
erase (by key) |
O(log n) |
map / set |
count |
O(log n) + occurrences |
map / set |
lower_bound, upper_bound |
O(log n) |
map / set |
begin, end |
O(1) |
map / set |
size, empty |
O(1) |
map |
operator[] |
O(log n) |
multiset |
erase(value) |
O(log n + k) where k = occurrences |
multiset |
erase(iterator) |
O(log n) |
| Container | Operation | Avg Time | Worst Time |
|---|---|---|---|
unordered_map/set |
find |
O(1) | O(n) |
unordered_map/set |
insert, emplace |
O(1) | O(n) |
unordered_map/set |
erase |
O(1) | O(n) |
unordered_map/set |
count |
O(1) | O(n) |
unordered_map/set |
size, empty |
O(1) | O(1) |
unordered_map/set |
rehash / reserve |
O(n) | O(n) |
| Container | Operation | Time Complexity |
|---|---|---|
stack |
push, pop, top |
O(1) |
stack |
size, empty |
O(1) |
queue |
push, pop |
O(1) |
queue |
front, back |
O(1) |
priority_queue |
push |
O(log n) |
priority_queue |
pop |
O(log n) |
priority_queue |
top |
O(1) |
priority_queue |
build from n elements | O(n) |
| Algorithm | Time | Notes |
|---|---|---|
sort |
O(n log n) | Introsort (QuickSort + HeapSort + InsertionSort) |
stable_sort |
O(n log n) | Merge sort; O(n log² n) if insufficient memory |
partial_sort |
O(n log k) | k = number of elements to sort |
nth_element |
O(n) avg | Introselect; not guaranteed sorted |
binary_search |
O(log n) | Requires sorted range |
lower_bound |
O(log n) | Requires sorted range |
upper_bound |
O(log n) | Requires sorted range |
find |
O(n) | Linear scan |
find_if |
O(n) | Linear scan |
count |
O(n) | |
count_if |
O(n) | |
reverse |
O(n) | |
rotate |
O(n) | |
unique |
O(n) | Requires sorted range for full dedup |
fill |
O(n) | |
iota |
O(n) | |
copy |
O(n) | |
transform |
O(n) | |
accumulate |
O(n) | |
partial_sum |
O(n) | |
min_element |
O(n) | |
max_element |
O(n) | |
next_permutation |
O(n) | |
shuffle |
O(n) |
| Operation | Time | Notes |
|---|---|---|
s[i], at(i) |
O(1) | |
length, size |
O(1) | |
push_back |
O(1) amortized | |
append, += |
O(k) | k = appended length |
substr |
O(k) | k = substring length |
find |
O(n·m) | n = string, m = pattern (naive) |
rfind |
O(n·m) | |
insert |
O(n) | |
erase |
O(n) | |
replace |
O(n) | |
compare |
O(min(n,m)) |
The operation takes the same amount of time regardless of input size.
// Examples:
arr[5] // Array index access
myMap[key] // Hash map lookup (amortized)
st.top() // Stack peek
pq.top() // Heap peek
v.push_back(x) // Vector push_back (amortized)
swap(a, b) // Variable swap
a + b // ArithmeticThe problem is repeatedly halved. Extremely fast — log₂(10⁹) ≈ 30.
// Examples:
binarySearch(arr, target) // Binary search
mySet.find(x) // BST search
myMap.lower_bound(k) // BST lower bound
priority_queue push/pop // Heap operations
// Quick mental check: does the loop variable double/halve? → O(log n)
for (int i = 1; i < n; i *= 2) ... // O(log n)
for (int i = n; i >= 1; i /= 2) ...// O(log n)Appears in number theory (checking primality, factorization).
// Check if n is prime
bool isPrime(int n) {
for (int i = 2; i * i <= n; i++) { // i goes up to √n
if (n % i == 0) return false;
}
return true;
}
// Loop runs √n times → O(√n)Each element is processed a constant number of times.
// Examples:
for (int x : arr) sum += x; // Single scan
find(v.begin(), v.end(), target) // Linear search
Building a hash map from n elements // O(n) insertions × O(1)
BFS/DFS on a graph // O(V + E) totalThe gold standard for sorting. Common in optimal algorithms.
// Examples:
sort(v.begin(), v.end()) // Merge sort / Introsort
stable_sort(...) // Merge sort
Building a heap from n elements using repeated push → O(n log n)
// Note: make_heap is actually O(n)!
// Many divide-and-conquer algorithms
// Many greedy algorithms that need a sorted preprocessing stepTwo nested loops over the input. Viable for n ≤ 10³.
// Examples:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) ... // Brute force pair checking
// Algorithms: Bubble sort, Insertion sort, Selection sort
// O(n²) DP problems (e.g., classic LCS is O(n²))
// Naive substring matching: O(n·m)Three nested loops. Viable only for n ≤ 200–300.
// Examples:
// Floyd-Warshall (all-pairs shortest path)
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
// Matrix chain multiplication DP
// Naive matrix multiplicationDoubles with each increment of n. Viable only for n ≤ 20–25.
// Examples:
// Enumerate all subsets (2ⁿ subsets of n elements)
for (int mask = 0; mask < (1 << n); mask++) { ... }
// Naive recursive Fibonacci
int fib(int n) { return n <= 1 ? n : fib(n-1) + fib(n-2); }
// Backtracking without pruning on binary decisionsGrows catastrophically. Viable only for n ≤ 10–12.
// Examples:
// Enumerate all permutations (n! permutations)
sort(v.begin(), v.end());
do {
process(v);
} while (next_permutation(v.begin(), v.end()));
// Traveling Salesman brute force
// n = 10 → 3,628,800 operations (viable)
// n = 15 → 1,307,674,368,000 operations (not viable)Slowest ────────────────────────────────────────── Fastest
O(n!) >> O(2ⁿ) >> O(n³) >> O(n²) >> O(n log n) >> O(n) >> O(√n) >> O(log n) >> O(1)
For n = 100:
O(n!) ≈ 9.3 × 10¹⁵⁷ ← Impossible
O(2ⁿ) ≈ 1.3 × 10³⁰ ← Way too slow
O(n³) = 1,000,000 ← Borderline
O(n²) = 10,000 ← Fast
O(n logn)≈ 664 ← Very fast
O(n) = 100 ← Very fast
O(log n) ≈ 7 ← Instant
O(1) = 1 ← Instant
Best Case: The input configuration that causes the algorithm to do the minimum work. Notated O(·) but conceptually represents Ω(·).
Worst Case: The input configuration that causes the algorithm to do the maximum work. The most important to know for interviews.
Average Case: Expected work over a random input distribution. Requires probabilistic analysis.
| Algorithm | Best Case | Average Case | Worst Case |
|---|---|---|---|
| Linear Search | O(1) (first element) | O(n/2) = O(n) | O(n) (not found) |
| Binary Search | O(1) (middle element) | O(log n) | O(log n) |
| Bubble Sort | O(n) (already sorted) | O(n²) | O(n²) |
| Insertion Sort | O(n) (already sorted) | O(n²) | O(n²) (reversed) |
| Quick Sort | O(n log n) (median pivot) | O(n log n) | O(n²) (sorted input, bad pivot) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) |
Hash Map find |
O(1) | O(1) | O(n) (all collide) |
BST find |
O(1) (root) | O(log n) | O(n) (skewed tree) |
// QuickSort picks a pivot and partitions around it
// Best case: pivot is always the median → perfectly balanced
// T(n) = 2T(n/2) + O(n) → O(n log n)
// Worst case: pivot is always min or max (e.g., sorted input, naive pivot)
// T(n) = T(n-1) + O(n) → O(n²)
// Avoiding worst case:
// 1. Random pivot: eliminates adversarial inputs
// 2. Median-of-three: pick pivot as median of first, middle, last
// 3. std::sort uses introsort: switches to heap sort if recursion depth > 2log(n)During interviews, always state WORST CASE complexity unless asked otherwise.
However, for certain algorithms you must know the distinction:
• Quick Sort: O(n log n) AVERAGE — but worst case O(n²)
→ Interviewer may probe: "can your solution be O(n²)?"
→ Answer: yes, with bad pivot; std::sort mitigates this with introsort
• Hash Map operations: O(1) AVERAGE — but worst case O(n)
→ Interviewer may probe: "is this always O(1)?"
→ Answer: amortized average; adversarial hashing can degrade it
• Union-Find: O(α(n)) AMORTIZED — practically O(1)
→ This is nearly always acceptable to state as O(1) per operation
This section teaches you how to talk about complexity — which is just as important as knowing it.
After writing a solution, proactively state:
"This runs in O([time]) time and O([space]) space.
The [time] comes from [brief explanation].
The [space] comes from [brief explanation]."
Good example:
"This solution runs in O(n log n) time and O(n) space.
The O(n log n) comes from sorting the input array.
The O(n) space is for the auxiliary sorted copy and the hash set
I'm using to track visited elements."
"Can you do better?"
Honest analysis:
- Know the theoretical lower bound for your problem type
- Comparison-based sorting → can't beat O(n log n)
- Searching unsorted array → can't beat O(n)
- Two-sum with sorting → O(n log n); with hash map → O(n)
- If already optimal: "I believe this is optimal because [reason]."
"What happens if n is very large?"
Walk through your complexity:
- "My O(n²) solution would be too slow for n = 10⁵.
I'd need to optimize it to O(n log n) using [approach]."
"What is the space complexity?"
Account for:
1. Output space (usually not counted)
2. Auxiliary data structures you created (arrays, maps, stacks)
3. Recursion call stack depth
- "The recursion depth is O(h) where h is the tree height,
which is O(log n) for a balanced tree and O(n) worst case."
When analyzing any piece of code, ask these in order:
1. Are there loops? How many nested levels?
One level → likely O(n)
Two levels → likely O(n²)
Three levels → likely O(n³)
2. Does any loop variable double/halve?
Yes → O(log n) for that loop
3. Is there recursion?
Write the recurrence and apply Master Theorem or substitution.
4. Are there STL operations inside loops?
sort inside loop: O(n) × O(n log n) = O(n² log n)
map.find inside loop: O(n) × O(log n) = O(n log n)
unordered_map inside loop: O(n) × O(1) = O(n)
5. What are the dominant terms?
Drop constants and lower-order terms.
// Problem: Find if any two elements in arr sum to target
// Approach: Sort + Two Pointers
bool twoSum(vector<int> arr, int target) { // Input: n elements
sort(arr.begin(), arr.end()); // ← O(n log n) time, O(log n) space (stack)
int l = 0, r = arr.size() - 1; // ← O(1) space
while (l < r) { // ← O(n) iterations (l and r meet in middle)
int sum = arr[l] + arr[r]; // ← O(1)
if (sum == target) return true;
else if (sum < target) l++;
else r--;
}
return false;
}
// Time: O(n log n) — dominated by sort; the while loop is O(n) which is less
// Space: O(log n) — sort uses O(log n) stack for recursion (introsort)
// — the two pointer variables are O(1)
// — note: input array is modified in-place (sorted)
// If we shouldn't modify input → make a copy: O(n) additional space