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

[Paolo Carlini]

Gabriel Dos Reis wrote:

> 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.

Humm.

I'm not sure to understand: you mean that often the requested
complexity class, such as N*log(N) for sort, has been chosen exactly
because *happen* to corresponds to "good" sorting algorithms, not
necessarily to those which have good asymptotic properties?

In other words, a mildly technical way to say: "please, for sort
provide something similar to quicksort"

Probably, this is exactly what you meant before by "common sense".

Right.

Still, this is the first time that I notice that a requirement in the
standard cannot strictly speaking be assessed. So to speak, there are
areas where it's "undecidable" ;) if a library, running on a finite
system, is conforming or not.

Are there other interesting examples??

Paolo.