Complexity nomenclature

[Jonathan M Davis via Digitalmars-d]

On Friday, 4 December 2015 at 09:17:07 UTC, Ola Fosheim Grøstad 
wrote:
> On Friday, 4 December 2015 at 09:09:35 UTC, ZombineDev wrote:
>> and space complexity (the correctness is given). Otherwise, 
>> designing large systems becomes impossible, because all large 
>> systems have hard performance requirements.
>
> I am sorry to say this, but hard performance requirements 
> require O(1) on everything.

Only when dealing with an arbitrary number of elements. O(n^2) 
could be fine if you know for a fact that you're always dealing 
with a very small number of elements. And some algorithms with 
worse complexity are actually faster than algorithms with lower 
complexity when dealing with a small number of elements - 
particularly since with a small number of elements, the 
coefficients can matter a lot more than n. So, really, to know 
which algorithm is appropriate, you need to know how it's 
actually going to be used in the program in question and how 
different algorithms perform there. O(1) is definitely better, 
but it's not necessarily required.

But yes, if you're dealing with an arbitrarily large number of 
elements, anything worse than O(1) isn't going to cut it if you 
have hard performance requirements.

> Big-Oh tells you essentially very little if it is more than 
> O(1). Quick sort and insertion sort are O(N^2), bucket sort is 
> O(N). That does not make bucket sort faster than quick sort or 
> even insertion sort on a specific case as it is dominated by 
> the number of possible values.

Yeah. Really, Big-Oh tells you something about the worst case 
with an arbitrary number of elements. What actually happens in 
the program depends heavily on the number of elements which are 
actually involved. With large numbers of elements, Big-Oh starts 
mattering, but if the number of elements isn't large, then 
coefficients and minor implementation details of an algorithm 
start mattering a lot more than its conceptual worst case.

Still, in general, it's better to be aware of algorithmic 
complexity and favor algorithms with lower complexity until you 
need to optimize the code based on your specific use case and 
determine that a higher complexity algorithm actually performs 
better in that specific use case.

- Jonathan M Davis