[mdxn]

People reading this write-up should keep in mind that the author uses the term "complexity class" incorrectly. When the author says this, they actually mean "worst case runtime". It never dives into space complexity, which is yet another complexity measure for evaluating the performance of these operations. In some spots they completely abuse big O notation to make it do things it is not supposed to. For example:

"O(==) is the complexity class for checking whether two values in the list are =="

This stuff needs to be fixed since it is only going to lead to later confusion (and embarrassment).

A complexity class is a set of problems that tend to be similar in resource requirements. O(f(n)), more or less, means asymptotically bounded from above by c*f(n) for some constant, c, as n -> inf. It is a general way to represent the asymptotic growth rate of functions and is NOT married to the concept of complexity classes.

[_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.

[repsilat]

> worst case runtime

For list append I think TFA lists amortized/average runtime, not worst-case.