Complexity nomenclature

[Ola Fosheim Grøstad via Digitalmars-d]

On Sunday, 6 December 2015 at 14:39:05 UTC, Timon Gehr wrote:
> Are you complaining that the given implementation does not 
> support 'min', or what are you trying to say here?

I am saying that comparing bounds is not the same as comparing 
running time of implemented algorithms. Insertion sort is both 
O(n^2) and O(n^3), but if you run it on a sorted array where each 
element have been swapped with neighbouring elements 16 times, 
then it is O(N).

So these derived bounds are too loose to be useful, generic 
algorithms cannot make use of them beyond the trivial case.

> BigO represents a set of functions. Comparing BigO checks for 
> subset inclusion.

But what can you use it for? When you compose algorithms and even 
run an optimizer over it, then combining a O(N^2) with O(N) kan 
turn into O(1). You need advanced compiler support for this to be 
valuable.

>> You can also get tighter bounds for specific input models.
>>
>
> Yes, you can.

Exactly, and when you compose/combine algorithms you often end up 
constraining the input model.