Date: Fri, 3 Feb 2023 11:03:03 +0300 (MSK) From: Alexander Monakov <amonakov@...ras.ru> To: musl@...ts.openwall.com Subject: Re: Re:Re:Re: Re:Re: qsort On Fri, 3 Feb 2023, David Wang wrote: > I think I was not reading the mail carefully enough, and did not notice the > O(1) "in place" space complexity. It's not correct to claim that musl smoothsort improves on qsort by having O(1) space complexity rather than O(log n). The storage for Leonardo numbers in musl smoothsort grows as O(log n) as well, musl just allocates enough for the maximum possible 'n'. Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.