Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

On 12/04/2015 02:50 AM, Minas Mina wrote:
> I agree -- putting the complexity (eh, running time) to the primitive's
> name seems like a bad idea.
>
> I believe that stability is a more important "feature" of a sorting
> algorithm than its running time, because you can make implications about
> it and use them for your own algorithms (I use it for implementing delta
> compression) and affects the output.
>
> Running time is still a good guarantee to have, but if `sort` runs
> O(n^2) or O(nlogn) is not going to affect how your output will look like!

Sort is almost always assumed to take n log n time. The problem is when 
you combine simpler operations, e.g. inserting elements at the front in 
a loop.

Andrei