Complexity Analysis
Big-O, space, amortized cost, and reading a problem's limits to know which algorithm will pass.
Big idea
Complexity analysis predicts how an algorithm's cost grows as the input grows, so you can tell before writing code whether it will finish in a second or in a week. Every other topic in this track uses it to compare approaches — learn to read it here first.
Think of it like
Two ways to find a name in a 1,000-page phone book. Reading every page from the start takes up to 1,000 page turns. Opening the middle, deciding which half the name is in, and repeating takes about 10. Double the book to 2,000 pages and the first way doubles to 2,000 turns while the second goes up by just one. Big-O is the language for that difference: not how fast either method is today, but how each one scales.
When you'll use it
| You're asked… | What complexity tells you |
|---|---|
| "Can you do better?" | Which growth rate to aim for next (n² → n log n → n) |
| "What's the time and space of your solution?" | The answer every interviewer expects at the end |
A problem with n ≤ 10^5 | That O(n²) — 10 billion steps — will time out |
| "Is this fast enough?" | Roughly 10⁸ simple steps per second as a budget |
Lessons
- 1What Big-O measuresCounting steps as the input grows, and why constants and small terms don't matter.
- 2The common growth ratesO(1) to O(n!) — what each looks like in code and how many steps it means at real input sizes.
- 3Working out the complexity of codeSequential blocks add, nested loops multiply, halving loops are log n, and recursion is branches to the power of depth.
- 4Space complexityExtra memory your algorithm needs — including the call stack you don't see.
- 5Amortized analysisWhy appending to a dynamic array is O(1) even though it sometimes copies everything.
- 6Reading a problem's constraintsUse n's upper limit to work out which complexity the intended solution must have.