I would not read these rules as anything like suggesting to write O(n^2) code. I think at best I'd read them as favoring O(n) instead of (1) for small n, but I

I would not read these rules as anything like suggesting to write O(n^2) code. I think at best I'd read them as favoring O(n) instead of (1) for small n, but I really think that "fancy" algorithms in this case doesn't mean obvious optimizations like this. If you can't guarantee n is small, I think it is entirely sensible to use a dictionary/hash table instead of looping over an array or list. As long as n is small the overhead is probably irrelevant, and it'll prevent surprises if n gets large as you said. And if the difference actually matters, you get back to rule 1 and 2 and measure first anyway.