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

[M.-A. Lemburg]

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
>