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

Jan Christoph Terasa christoph at kohlio.de
Mon Aug 17 03:49:03 EDT 2020

Hi Marc-Andre,

sorry, my user name is JanChristophTerasa, using this mail address.


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.
>On 17.08.2020 08:57, Jan Christoph Terasa wrote:
>> Moin moin,
>> I partook in a discussion on stack overflow regarding time complexity
>> popping the first element off of a list:
>> As paxdiablo correctly points out there, popping anything except the
>> last element involves a memmove/memcpy , which essentially has a
>> 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
>> kind of misleading. It introduces k as the "value of the parameter",
>> 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
>> list is O(k). From my understanding the statement "The Average Case
>> assumes parameters generated uniformly at random" is essentially what
>> stated above, so the value in the table should *not* depend (only) on
>> 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
>> 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
>> 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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pydotorg-www/attachments/20200817/c7384f83/attachment-0001.html>

More information about the pydotorg-www mailing list