Capstone: Counting Steps & Big-O Intuition
Lesson 5 of 5 · View course roadmap
Learn the idea
Why does one script finish instantly and another hang forever on the same data? Count the steps, not the lines:
- One loop over n items → about n steps — double the data, double the time
- A loop inside a loop → n × n steps — double the data, quadruple the time
- Halving like binary search → log n steps — a million items feels like twenty
Engineers write these as O(n), O(n²) and O(log n) — "Big-O" — but the notation is just shorthand for the growth you can now measure yourself. The instinct to ask "how does this grow when the data grows?" is the single most interview-tested skill in programming, and you can build it with two counters.
Where you'll use this
Big-O is the shared language of code review and system design: 'this endpoint is O(n²) on cart size' is a complete bug report. It predicts at design time what profilers confirm in production.
Common mistakes
- Judging speed by lines of code — one nested loop outweighs fifty straight-line statements.
- Hiding a loop inside a loop accidentally:
if x in big_listinside a for is O(n²) in disguise. Use a set. - Optimising an O(n) function when the real cost is an O(n²) block elsewhere — count first, optimise second.
Pro tip
Memorise three growth feelings: log n (barely notices data), n (scales linearly), n² (fine at 100, dead at 100,000). Most day-to-day performance calls need nothing more.
Try it yourself
The lesson example is loaded and ready — press Run, then change something and run it again. Breaking it is part of learning. Want a clean slate? Tap “New blank”.
Output appears here…
Pass the challenge +45 XP
For 20 items, count the operations a single loop performs, then the operations a nested (loop-in-loop) pass performs. Print both counts, then print Nested loops grow fast!
20 400 Nested loops grow fast!
Increment a counter inside each loop body. The nested version increments inside the inner loop.
items = list(range(20))
ops = 0
for a in items:
ops += 1
print(ops)
ops = 0
for a in items:
for b in items:
ops += 1
print(ops)
print("Nested loops grow fast!")
Run your code to check it…
Check your understanding
Your notes (saved on this device)
Tip: use ← and → to move between lessons, ⌘K to search everything.