[_droptable_]

> When the author says this, they actually mean "worst case runtime".

Actually, the author says that all dict operations take O(1) time, which is the best (or average) case and not the worst case. I think it should at least mention the worst case! No hash table exists where you get worst case O(1) (non-amortized) for all three of insertion, deletion, and lookup. You either have to resize the table at some point or you have to deal with hash collisions.

(BTW, I've been asked this question numerous times in job interviews and answering O(1) without qualifying the statement is definitely wrong.)

See https://wiki.python.org/moin/TimeComplexity

and http://cs.stackexchange.com/questions/249/when-is-hash-table...

[kevinwang]

This is a good point. The reason for this error in the notes, I believe, is that they are for an introductory programming class at this university and introducing this nuance may put off some students with its complexity.