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

[Jan Christoph Terasa]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/pydotorg-www/attachments/20200817/c7384f83/attachment-0001.html>