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@python.org https://mail.python.org/mailman/listinfo/pydotorg-www
