I'm seeing a lot of great discussion on this thread, but I'd like to point out that you should NEVER rely on memorization to know the asymptotic bounds of opera

I'm seeing a lot of great discussion on this thread, but I'd like to point out that you should NEVER rely on memorization to know the asymptotic bounds of operations on data structures. You should understand how that data structure works and then derive the running time from that. People seem to know hash sets use O(1) lookup, trees use O(log(n)), and so forth. In reality, they have an in depth understanding of the underlying implementation and are rederiving their answers on the spot with simple mental calculations.