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