Big O, Ω and Θ, best/average/worst cases, amortized analysis, recursive complexity and the Master Theorem — the language every interview answer is graded in.
0 of 8 lessons checked off
Introduction
What it is
Complexity analysis measures how an algorithm's running time and memory grow as the input grows. Big O notation captures that growth rate while deliberately ignoring constant factors and small inputs.
Big O is an upper bound ('grows no faster than'), Big Omega (Ω) a lower bound, and Big Theta (Θ) a tight bound. In interviews, 'Big O' is used loosely to mean the tight bound of the typical case — but you should know the formal difference.
Why it matters
Constraints are a coded message: n ≤ 10⁵ means roughly 'find an O(n log n) or O(n) algorithm', because ~10⁸ simple operations per second is a safe mental budget.
Every interview answer ends with 'time and space complexity?' — fluency here is non-negotiable.
How it works
Count how work scales, not what it costs once: a loop over n items is O(n); two nested loops are O(n²); halving each step is O(log n); doing log n work n times is O(n log n).
Drop constants and lower-order terms: 3n² + 10n + 512 is O(n²). They matter in production tuning, not in growth-rate analysis.
For recursion, write the recurrence: T(n) = 2T(n/2) + O(n) (merge sort) solves to O(n log n) by the Master Theorem.
Where it's used
The difference between O(n²) and O(n log n) is the difference between a report that takes 3 hours and one that takes 2 seconds once n reaches a million rows — this is why database indexes and sort-merge joins exist.
In interviews
Stating the brute-force complexity first, then improving it, is the standard interview arc.
Amortised analysis explains why dynamic-array append and hash-table inserts count as O(1).
Analogy: Big O is like describing a road-trip by its speed limit rather than a specific day's traffic: it tells you how travel time scales with distance, ignoring one-off delays.
Interactive diagram
Work done at n = 1…32 for the four rates you'll quote most. Note how n² dwarfs everything.
1
1
2
3
4
5
O(log n) growth
Doubling the input adds ONE unit of work — binary search territory. Work at n = 1, 2, 4, 8, 16, 32: 1, 1, 2, 3, 4, 5.
1 / 5
Lessons in this topic
Check off lessons as you go — your progress is saved in this browser.
Big O notation
Upper-bound growth: definition, dropping constants and lower-order terms.
20 min
Big Omega and Big Theta
Lower bounds and tight bounds; what 'binary search is Θ(log n) worst case' actually claims.
10 min
Best, average, and worst cases
Same algorithm, three curves: quicksort is O(n log n) average yet O(n²) worst.
15 min
Space complexity
Auxiliary space vs input space; the recursion stack counts.
15 min
Amortized analysis
Why n appends into a doubling array cost O(n) total — accounting, not optimism.
15 min
Recursive complexity and recursion trees
Turning recursion into recurrences and reading total work off the tree.
20 min
The Master Theorem
Solving T(n) = aT(n/b) + f(n) by comparing f with n^log_b(a).
15 min
Complexity comparison chart
O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!) with example algorithms.
10 min
Operations
Reading complexity off code
The four shapes that cover most code you will ever analyse.
Reading complexity off code
1# O(n): one pass2total=03forxinnums:# n iterations × O(1) work4total+=x56# O(n^2): nested passes over the same input7pairs=08foriinrange(n):9forjinrange(i+1,n):# n(n-1)/2 iterations → O(n^2)10pairs+=11112# O(log n): the input shrinks by a constant factor each step13whilen>1:14n//=2# ~log2(n) iterations1516# O(n log n): log-n work done n times (or n work log-n times)17forxinnums:# n iterations18heapq.heappush(heap,x)# × O(log n) each
Time: —Space: —
Edge cases
Two sequential loops are O(n) + O(n) = O(n), not O(n²) — nesting multiplies, sequence adds.
A loop that runs n times doing `s += char` on a string is O(n²): the hidden copy counts.
Common mistakes
Calling a solution with a sort inside 'O(n)' — the sort dominates at O(n log n).
Ignoring the cost of slicing: nums[1:] copies O(n) elements every recursive call.
Amortized analysis of list.append
Doubling arrays make appends O(1) on average even though single appends occasionally cost O(n).
Amortized analysis of list.append
1# A dynamic array doubles capacity when full.2# Appending n items causes resizes at sizes 1, 2, 4, ..., n/2.3# Total copy work: 1 + 2 + 4 + ... + n/2 < n4# So n appends cost O(n) total → O(1) amortised each.56items=[]7foriinrange(1_000_000):8items.append(i)# O(1) amortised, despite occasional O(n) resizes
Time: O(1) amortised per appendSpace: O(n)
Edge cases
Amortised O(1) is not worst-case O(1): a single append can still stall on a resize — relevant for latency-sensitive systems.
Common mistakes
Claiming hash-map operations are 'always O(1)' — they are O(1) average/amortised, O(n) worst case under collisions.
The Master Theorem in practice
For T(n) = a·T(n/b) + f(n), compare f(n) against n^log_b(a) and take the dominant side.
The Master Theorem in practice
1# T(n) = a * T(n/b) + f(n), c = log_b(a)2#3# f(n) smaller than n^c → T(n) = Θ(n^c)4# f(n) equal to n^c → T(n) = Θ(n^c · log n)5# f(n) larger than n^c → T(n) = Θ(f(n))6#7# Merge sort: T(n) = 2T(n/2) + Θ(n) c = 1, equal → Θ(n log n)8# Binary search: T(n) = 1T(n/2) + Θ(1) c = 0, equal → Θ(log n)9# Karatsuba: T(n) = 3T(n/2) + Θ(n) c ≈ 1.585, f smaller → Θ(n^1.585)
Time: —Space: —
Edge cases
The theorem needs subproblems of equal size n/b; T(n) = T(n−1) + O(1) (linear recursion) is outside it — that one just sums to O(n).
Common mistakes
Applying it to unbalanced recursions like quicksort's worst case T(n) = T(n−1) + O(n), which solves to O(n²) by summation, not the Master Theorem.
Complexity analysis
Operation
Best
Average
Worst
Space
Binary search
O(1)
O(log n)
O(log n)
O(1)
Single scan / two pointers
O(n)
O(n)
O(n)
O(1)
Merge sort
O(n log n)
O(n log n)
O(n log n)
O(n)
Quick sort
O(n log n)
O(n log n)
O(n²)
O(log n)
Subset enumeration
O(2ⁿ)
O(2ⁿ)
O(2ⁿ)
O(n)
Permutation enumeration
O(n!)
O(n!)
O(n!)
O(n)
Reference points to calibrate against. If your answer is right of merge sort on this table, say why the problem forces it.
Python implementation
Production-quality code with type hints, validation, and docstrings.
Constraint → target complexity translator
1deftarget_complexity(n:int)->str:2"""Rule-of-thumbmappingfrominputsizetothecomplexity3aninterviewermostlikelyexpects(budget~10^8operations)."""4ifn<=12:5return"O(n!) or O(2^n) — brute force / backtracking is intended"6ifn<=25:7return"O(2^n) with pruning or meet-in-the-middle"8ifn<=500:9return"O(n^3) is acceptable"10ifn<=5_000:11return"O(n^2) is acceptable"12ifn<=200_000:13return"O(n log n) — sort, heap, or divide and conquer"14ifn<=10_000_000:15return"O(n) — single pass, hashing, two pointers"16return"O(log n) or O(1) — binary search or math"171819fornin(10,1_000,100_000,10**9):20print(f"n = {n:>12,} → {target_complexity(n)}")
What interviewers expect you to know
Definitions interviewers probe
O(g): grows no faster than g (upper bound). Ω(g): no slower (lower bound). Θ(g): both — a tight bound.
Worst/average/best case are properties of inputs; O/Ω/Θ are properties of bounds. 'Worst-case Θ(n log n)' is a coherent, precise claim.
Space complexity counts auxiliary memory — and the recursion stack is auxiliary memory.
Classic follow-ups
"Can you do better?" — know the floor: comparison sorting can't beat Ω(n log n); searching sorted data can't beat Ω(log n) with comparisons.
"Why is hash-map insert O(1) if resizing is O(n)?" — amortised analysis: doubling spreads resize cost over the inserts that caused it.
"What's the complexity of your recursion?" — branches^depth for the tree size, times per-node work; then say whether memoization collapses it.
How to talk about it
State complexity unprompted, right after your approach: 'this is O(n) time, O(1) extra space.' It is the cheapest strong signal in the interview.
When comparing approaches, compare both axes — 'the hash map is O(n) time but O(n) space; sorting is O(n log n) time but O(1) space' — and let constraints pick.
Common mistakes
Dropping the log
n heap operations or a sort inside a loop is O(n log n), not O(n). Say where every log comes from: halving or a height-log n structure.
Counting only time, not space
A recursive DFS on a path-shaped tree holds O(n) stack frames. 'O(1) extra space' with recursion is almost always wrong.
Hidden O(n) inside 'one line'
Slicing (a[1:]), `in` on a list, str concatenation, list.insert(0, x) — each is a linear operation dressed as a primitive.
Best case quoted as the answer
'Bubble sort is O(n)' is only its best case. Default to worst case unless asked otherwise, and label any average-case claim.
Treating Big O as a speed guarantee
O(1) with a huge constant can lose to O(log n) at practical sizes; Big O ranks growth, not raw speed.
Practice problems
Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.
No practice problems are configured for this topic yet.
6 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.
Frequently asked questions
Do interviewers care about the difference between O and Θ?
Rarely in wording, but they care that you know worst vs average case. Saying 'quicksort is O(n log n)' without 'average case' will draw a follow-up at strong companies.
Does Big O include constants?
No — O(2n) and O(n) are the same class. Constants matter for real performance but not for growth-rate classification, which is what Big O measures.
How precise should my space analysis be?
State auxiliary space and include the recursion stack. 'O(n) for the hash map plus O(h) recursion' is exactly the precision expected.
Summary & cheat sheet
Key takeaways
Big O = upper bound on growth; drop constants and lower-order terms.