<html><head></head><body>Hi Marc-Andre,<br><br>sorry, my user name is JanChristophTerasa, using this mail address.<br><br>regards,<br>Christoph <br><br><div class="gmail_quote">On August 17, 2020 9:42:45 AM GMT+02:00, "M.-A. Lemburg" <mal@python.org> wrote:<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<pre class="k9mail">Hi Christoph,<br><br>we can make you editor, but need your wiki user name in order<br>to do so.<br><br>Thanks,<br>Marc-Andre<br><br>On 17.08.2020 08:57, Jan Christoph Terasa wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 1ex 0.8ex; border-left: 1px solid #729fcf; padding-left: 1ex;">Moin moin,<br><br>I partook in a discussion on stack overflow regarding time complexity of<br>popping the first element off of a list:<br><a href="https://stackoverflow.com/questions/63445069/what-are-effects-on-overhead-of-using-list-pop0">https://stackoverflow.com/questions/63445069/what-are-effects-on-overhead-of-using-list-pop0</a><br><br>As paxdiablo correctly points out there, popping anything except the<br>last element involves a memmove/memcpy , which essentially has a runtime<br>of O(N-k), with k being the argument. Assuming choosing k at random<br>uniformly, this is O(N/2) = O(N).<br><br>During the discussion I referred to the Python Wiki page<br><a href="https://wiki.python.org/moin/TimeComplexity">https://wiki.python.org/moin/TimeComplexity</a> and the information there is<br>kind of misleading. It introduces k as the "value of the parameter", and<br>also states that "The Average Case assumes parameters generated<br>uniformly at random" It then shows in the table that average and<br>amortized worst time complexity of popping intermediate elements from a<br>list is O(k). From my understanding the statement "The Average Case<br>assumes parameters generated uniformly at random" is essentially what I<br>stated above, so the value in the table should *not* depend (only) on k,<br>but on N, and it should thus be O(N) in both cases.<br><br>I think stating O(k) is misleading, since it looks like the complexity<br>depends only on k, and thus popping the first element should be O(1),<br>while in reality it depends on N as well (being N-k), and in the<br>"average case" we get O(N) as shown above. In general it could be<br>helpful to add a footnote explanation of how pop behaves, since it<br>depends both on the size of N and k, and it certainly is not<br>proportional to k, quite the contrary.<br><br><br><br>If you are willing to give me edit permissions for that page I can help<br>with some suggestions (I hope that page has a "Discussion" subpage to<br>"stage" some proposed changes first).<br><br><br>kind regards,<br>Christoph Terasa<hr>pydotorg-www mailing list<br>pydotorg-www@python.org<br><a href="https://mail.python.org/mailman/listinfo/pydotorg-www">https://mail.python.org/mailman/listinfo/pydotorg-www</a><br><br></blockquote></pre></blockquote></div><br>-- <br>Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail gesendet.</body></html>