N*log(N) doesn't exist (Re: [RFC] Vector (string?) growth...)

[Gabriel Dos Reis]

Paolo Carlini <pcarlini@suse.de> writes:

| Gabriel Dos Reis wrote:
| 
| > | Therefore, for every possible _finite_ N, how we can possibly assess if
| > | an implementation is conforming without looking at the source code?
| >
| > I have always thought that those complexity requirements were good
| > pratical hints to implementors as what minimum efficiency their common
| > sense should guide them to aim at. It looks like "common sense" was
| > not well defined ;-)
| 
| ;-)
| 
| In my reading, those complexity requirements, un-enforceable (is it good
| english? ;) without looking at the source code, are just a subliminal but
| very strong argument in favor of Open Source, if not of Free Software ;-)

I'm not sure.

Quicksort is not the asymptotically fastest sorting algorithm, but for
a failry good range of data, it performs well.  On the other hand I
would not use it for very large sequences.  

(Note: I'm a big believer of unrestricted access to software) 

-- Gaby