Lesson 18 of 48
Arrays, lists, dicts, and Big O
How data sits in memory, and how to say what it costs.
Big O is not decoration: it is the difference between a program that finishes and one that does not. Knowing why a dict lookup is constant-time and a list scan is not will shape every structure you reach for.
Do this
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.
The question that unlocks the next lesson
Why is a hash table lookup typically O(1) but O(n) in the worst case?
- ABecause hashing is slow for large keys
- BBecause if every key collides into one bucket, lookup degenerates into scanning a list
- CBecause the table must be re-sorted after each insert
- DBecause O(1) only holds for integer keys