"in" everywhere

[Seth Hoenig]

2010/10/8 "Jérôme M. Berger" <jeberger at free.fr>

> Steven Schveighoffer wrote:
> > On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke <rainerd at eldwood.com>
> > wrote:
> >
> >> On 10/7/2010 13:57, Andrei Alexandrescu wrote:
> >>> On 10/7/10 14:40 CDT, bearophile wrote:
> >>>> Another solution is just to accept O(n) as the worst complexity for
> >>>> the "in" operator. I don't understand what's the problem in this.
> >>>
> >>> That means we'd have to define another operation, i.e. "quickIn" that
> >>> has O(log n) bound.
> >>
> >> Why?
> >>
> >> I can't say I've ever cared about the big-O complexity of an operation.
> >
> > Then you don't understand how important it is.
>
>         If big O complexity is so important, then why does everyone use
> quicksort (which is O(n**2)) and not heap sort or merge sort (which
> are O(n*log(n)))?
>
>                Jerome
> --
> mailto:jeberger at free.fr
> http://jeberger.free.fr
> Jabber: jeberger at jabber.fr
>
>

Because on average quicksort is faster than heap sort, and uses much less
space than merge sort. Also, trivial guards can be put in place to avoid
running quicksort in a worst case (pre-sorted data) scenario.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d/attachments/20101008/c1d472a8/attachment.html>