[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20170915191846.wvjp2x4u4nobhi52@voyager>
Date: Fri, 15 Sep 2017 21:18:46 +0200
From: Markus Wichmann <nullplan@....net>
To: musl@...ts.openwall.com
Subject: Re: Wrong info in libc comparison
On Wed, Sep 13, 2017 at 03:53:06PM -0400, Rich Felker wrote:
> If you're considering big-O, where n->infinity (or at least to the
> largest value that can fit in memory), malloc most certainly has
> failed (because the array to be sorted already filled memory) and
> you're looking at the "fallback" case.
>
I think we're getting sidetracked here. Every libc worth its salt uses a
loglinear sorting algorithm. Thus they are all equal in that regard.
Only exception to this I've ever seen is uclibc, which uses Shell sort
with Pratt's sequence, which is O(sqrt(n^3)) instead (is there a snappy term
for this complexity?)
Besides, big-O is also about the behavior of time on change of space
(what happens if the problem doubles in size?).
> Maybe the comparison of sort algorithm used is interesting for reasons
> other than just big-O though, in which case mentioning the "merge
> (when it fits in memory)" would probably be helpful.
>
> Rich
Algorithms can be compared on a number of metrics, and just the name
doesn't tell us much (e.g. quicksort with naive "first element" pivot
selection has a pathological case on sorted input, while quicksort with
med3 pivot selection handles that very well). If you really want to know
something specific, you'll have to look it up in source, anyway.
But, if you do give a name, make sure it's the right one.
Ciao,
Markus
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.
