Re:Complexity of Python Operations (2013)
by _droptable_ on Thursday January 14, 2016 @08:18AM
(#10901154)
> 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...
Re:Complexity of Python Operations (2013)
by kevinwang on Thursday January 14, 2016 @05:38PM
(#10905307)
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.
"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.