"in" everywhere

[Lutger]

"Jérôme M. Berger" wrote:

> 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

For average case big O and dwarfing heap/merge sort in the constant factor. But 
in fact its not totally true that everyone uses quicksort pur sang: most sort 
implementations deal with the worst case of quicksort, by switching to heapsort  
for example. It is exactly because of this behavior.