I've added you to the editors, so you should be all set... On 17.08.2020 09:49, Jan Christoph Terasa wrote: > Hi Marc-Andre, > > sorry, my user name is JanChristophTerasa, using this mail address. > > regards, > Christoph > > On August 17, 2020 9:42:45 AM GMT+02:00, "M.-A. Lemburg" > <m...@python.org> wrote: > > 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 > > > -- > Diese Nachricht wurde von meinem Android-Mobiltelefon mit K-9 Mail > gesendet.
-- Marc-Andre Lemburg Python Software Foundation http://www.python.org/psf/ http://www.malemburg.com/ _______________________________________________ pydotorg-www mailing list pydotorg-www@python.org https://mail.python.org/mailman/listinfo/pydotorg-www
