[pydotorg-www] Edit Permission?

[Chris Angelico]

On Mon, May 18, 2020 at 2:56 AM Robert DiPietro <rdipietro at 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