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

[Gabriel Dos Reis <gdr at integrable-solutions dot net>]

Paolo Carlini <pcarlini@suse.de> writes:

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

I'm saying that those bounds were not choosen out of the hat.  

For example, the standard could have required O(1) and given a
footnote saying that 

   We're are aware of the huge amount of research wnet that into sorting
   these last decades and the mathematical meaning of asymptotics.
   However, any instance of sorting involves a finite length sequence 
   and there cannot be more than std::numeric_limits<std::size_t>::max()
   elements in a sequence.  Therefore, any sorting algorithm has a
   complexity time bounded by the worst case for the maximal
   sequence. An implementation can define that time to be the constant
   in the complexity factor. 


I'm saying that the complexity requirements correspond more or less to
those of "good" (good to be defined in appropriate way) algorithms
known at the time the standard was defined.

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

I'm saying that if my favorite vendor knows of foosort and a "good"
algorithm with asymptotic complexity "N * lg(N)" and that such an
algorithm performs very bad compared to foosort for inputs with length
< 100, then I wouldn't appreciate he always uses the asymptotically
fast algorithm where foosort would have been faster.  

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

The standard is not written with all mathematical rigour, so I don't
know how you define "strctly speaking assessed".  

-- Gaby