On Mon, May 18, 2020 at 2:56 AM Robert DiPietro <rdipie...@gmail.com> wrote: > > Hi all, > > Thank you for maintaining these pages. The TimeComplexity page > (https://wiki.python.org/moin/TimeComplexity) has been especially helpful to > me over time. > > I signed up to make an edit to this page, by adding the following row to the > top of the dict table: > > Operation Average Case Amortized Worst Case > x in d O(1) O(n) > > Small aside 1: I do realize that the reader can potentially figure this out > from this page. But to do this, the reader needs to scroll up to the > seemingly distinct set table, to catch the statement "See dict -- the > implementation is intentionally very similar." And even then the reader is > left wondering if x in d is actually constant on average. >
Seems like a worthwhile addition. > Small aside 2: I have not looked at the underlying dict code, but I did > empirically verify that x in d is indeed constant on average. I assume that > it's based on hashing, which then would also imply the same > amortized-worst-case complexity as set. > Yes, it is (and lots of Python assumes that "x in d" is going to be fast - for instance, name lookups can go through several dict-based namespaces). Given that "Get Item" is explicitly listed as having constant average time, you can safely assume that a boolean containment check won't be any worse. > My wiki name is RobertDiPietro > Thanks! You should now be able to make changes. BTW, speaking of the source, it seems to be linking to something fairly ancient. I don't even know which Python release that's from, but it seems to be from Subversion. Feel free to replace that with a link to GitHub if you wish. ChrisA _______________________________________________ pydotorg-www mailing list pydotorg-www@python.org https://mail.python.org/mailman/listinfo/pydotorg-www
