[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <841ab767-8f7c-4a4a-23ed-95901528a1b6@ispras.ru>
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.
