2023-12-18
- I started out with one junk drawer
- Find anything in it was O(N) in the number of things in the drawer, since I had to look at each one
- If I had N drawers, I could sort of make it O(1)
- Really it’s O(N) with a much lower prefactor
- I still have to read all the drawer labels
- For the purpose of finding things, reading labels is effectively free
- But I don’t have N drawers
- Let’s say I have M << N drawers instead
- I can create groupings, which may or may not be arbitrary
- Label each drawer with all the things in its group
- Assuming reading labels remains free, finding things is now O(N/M)
- (Here the categories are a stand-in for the hash value)
- This actually happened