[pydotorg-www] TimeComplexity page on the wiki, pop_intermediate for lists

[M.-A. Lemburg]

I've added you to the editors, so you should be all set...

On 17.08.2020 09:49, Jan Christoph Terasa wrote:
> Hi Marc-Andre,
> 
> sorry, my user name is JanChristophTerasa, using this mail address.
> 
> regards,
> Christoph
> 
> On August 17, 2020 9:42:45 AM GMT+02:00, "M.-A. Lemburg"
> <mal at python.org> wrote:
> 
>     Hi Christoph,
> 
>     we can make you editor, but need your wiki user name in order
>     to do so.
> 
>     Thanks,
>     Marc-Andre
> 
>     On 17.08.2020 08:57, Jan Christoph Terasa wrote:
> 
>         Moin moin,
> 
>         I partook in a discussion on stack overflow regarding time
>         complexity of
>         popping the first element off of a list:
>         https://stackoverflow.com/questions/63445069/what-are-effects-on-overhead-of-using-list-pop0
> 
>         As paxdiablo correctly points out there, popping anything except the
>         last element involves a memmove/memcpy , which essentially has a
>         runtime
>         of O(N-k), with k being the argument. Assuming choosing k at random
>         uniformly, this is O(N/2) = O(N).
> 
>         During the discussion I referred to the Python Wiki page
>         https://wiki.python.org/moin/TimeComplexity and the information
>         there is
>         kind of misleading. It introduces k as the "value of the
>         parameter", and
>         also states that "The Average Case assumes parameters generated
>         uniformly at random" It then shows in the table that average and
>         amortized worst time complexity of popping intermediate elements
>         from a
>         list is O(k). From my understanding the statement "The Average Case
>         assumes parameters generated uniformly at random" is essentially
>         what I
>         stated above, so the value in the table should *not* depend
>         (only) on k,
>         but on N, and it should thus be O(N) in both cases.
> 
>         I think stating O(k) is misleading, since it looks like the
>         complexity
>         depends only on k, and thus popping the first element should be
>         O(1),
>         while in reality it depends on N as well (being N-k), and in the
>         "average case" we get O(N) as shown above. In general it could be
>         helpful to add a footnote explanation of how pop behaves, since it
>         depends both on the size of N and k, and it certainly is not
>         proportional to k, quite the contrary.
> 
> 
> 
>         If you are willing to give me edit permissions for that page I
>         can help
>         with some suggestions (I hope that page has a "Discussion"
>         subpage to
>         "stage" some proposed changes first).
> 
> 
>         kind regards,
>         Christoph Terasa
>         ------------------------------------------------------------------------
>         pydotorg-www mailing list
>         pydotorg-www at python.org
>         https://mail.python.org/mailman/listinfo/pydotorg-www
> 
> 
> -- 
> Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail
> gesendet.

-- 
Marc-Andre Lemburg
Python Software Foundation
http://www.python.org/psf/
http://www.malemburg.com/