Rung 18
Arrays, lists, dicts, and Big O
How data sits in memory, and how to say what it costs.
Best attempted after 8. Python: files and automation. Nothing stops you trying this now — the gate will tell you if you were right.
The gate
Implement a hash table from scratch — no dict, no set — with working collision handling. State the cost of insert and lookup in the typical case and in the worst case, then construct an input that actually triggers the worst case and measure it.
Nobody checks this but you. Do it honestly and the rungs above hold; do it loosely and they will not, somewhere further up where the cause is much harder to find.
You have been using lists and dictionaries since rung 7 without asking what they cost. This rung asks. The answer is not a detail: it is the difference between a program that finishes and one that appears to hang.
Big O is the notation for that answer. It deliberately throws away constants and keeps only how cost grows with size — because at the scales that matter, growth is what decides everything.
Why this is on the ladder
Because rung 9's exponents are about to become concrete. An O(n²) routine on a
thousand items is a million operations, which is nothing; on a million items it
is a trillion, which is your afternoon. Same code, and the only thing that
changed was n.
And because a hash table is the most useful structure in everyday programming.
Building one — rather than importing one — is what turns dict from magic into
a mechanism you could rebuild.
Do this
Build the hash table. A list of buckets; a hash function mapping a key to an
index; collision handling by chaining each bucket as a small list. Implement
set, get, and delete. Test it against a real dict on a few thousand
random keys — same answers, every time.
Now reason about cost. With keys spread evenly, a bucket holds roughly one item,
so lookup is O(1) — the cost does not grow with n. That is the whole reason the
structure exists.
Then break it deliberately. Write a hash function that returns 0 for everything.
Every key lands in one bucket, the table degenerates into a single list, and
lookup becomes O(n). Measure both versions at several sizes and watch the curves
separate. That measurement is the gate: you have made the difference between
O(1) and O(n) something you observed rather than something you were told.
Where people get stuck
Confusing the typical case with the guarantee. A hash table is O(1) on average and O(n) in the worst case, and the gap is not academic — it is the basis of a real class of denial-of-service attack, where an attacker sends keys chosen to collide.
The other snag is timing badly: measuring one run of a fast operation tells you about your machine's noise, not your code. Time many repetitions, and compare across sizes rather than trusting any single number.