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

[Jan Christoph Terasa]

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