Algorithm Dojo — Algorithms & Big-O
Six classic algorithms — each one measured as you write it.
How to play
Write the function and press Run. The game then runs it over inputs of growing size and counts how many elements your code actually touches, draws the growth, and names the curve: O(1), O(log n), O(n), O(n log n) or O(n²). Three of the levels will refuse a correct answer that does too much work, and tell you exactly how far over budget you were.
The measurement is a count, not a stopwatch. Timing in a browser is noisy and depends on the machine; counting element accesses is deterministic, identical here and on your computer, and is the same quantity a textbook means when it says "operations".
What each level teaches
- Look at everything — linear search, the O(n) baseline everything else is measured against.
- Halve it every time — binary search: about 21 look-ups into a list of 1,024.
- Sort it yourself — selection sort, and what two nested loops cost.
- Two that add up — a set turns a nested loop into one pass.
- The first repeat — "have I seen this?" is a set question, not a search.
- What they have in common — converting once beats searching repeatedly.
The numbers you will actually see
| Level | n = 16 | n = 1024 | Curve |
|---|---|---|---|
| Linear search | 16 | 1,024 | O(n) |
| Binary search | 9 | 21 | O(log n) |
| Selection sort | 272 | — | O(n²) |
Binary search is the one worth sitting with. Going from 16 items to 1,024 — sixty-four times the data — costs nine extra look-ups. Multiply the data by a thousand again and it costs ten more. That is what logarithmic means, and it is why sorted data is worth so much.
Big-O in one paragraph
It describes how the work grows as the input grows, ignoring constants and the machine. O(n) means doubling the input doubles the work. O(n²) means doubling it quadruples the work — fine for a hundred items, impossible for a million. O(log n) barely grows at all. The constants it ignores are real, so an O(n²) algorithm can beat an O(n) one on small inputs; what Big-O tells you is which one stops working first as the data gets bigger.
The trade this game keeps making
Levels 4, 5 and 6 are all the same move: spend a little memory on a set or a dict, and
turn a search into a look-up. That one trade — from scanning a list to hashing a key — is probably the highest-value
habit in everyday programming, because it converts the nested loop you were about to write into a single pass.
When you want more to practise on, the 20 Python practice exercises have worked solutions, and Code Golf comes at the same code from the opposite direction: shortest rather than fastest.
Frequently asked questions
What is Big-O notation?
A description of how an algorithm's work grows as its input grows, ignoring constant factors. O(n) means the work is proportional to the input size; O(n²) means it grows with the square of it.
How does this game measure complexity?
It counts how many elements your function touches at several input sizes, then fits that growth to the nearest familiar curve. Counting is deterministic, unlike timing, which varies by machine and load.
Why is binary search so much faster than linear search?
Because it halves the remaining range at every step, so a list of 1,024 takes about ten look-ups instead of 1,024. It only works on sorted data, which is what buys the speed.
Is O(n²) always bad?
No. For small inputs the constants matter more than the curve, and a simple quadratic algorithm can beat a clever linear one. It becomes bad when the data grows — which it usually does.
When should I use a set or dict instead of a list?
Whenever you are asking 'is this in there?' repeatedly. Membership in a list scans it; in a set it is effectively instant, which is what turns a nested loop into a single pass.
Keep going
- Read the algorithms & big-o tutorial — the written explanation behind every level here.
- Variable Vault — variables & data types.
- Operator Arcade — numbers & operators.
- String Surgeon — strings & slicing.
- 20 Python practice exercises with worked solutions.
Take the games with you
Coding Python packs a real Python 3 compiler, 30 example programs, 112 quiz questions and 12 self-checking challenges into one free Android app.
Get it on Google Play