Complexity nomenclature

[ZombineDev via Digitalmars-d]

On Friday, 4 December 2015 at 09:50:15 UTC, Ola Fosheim Grøstad 
wrote:
> On Friday, 4 December 2015 at 09:33:42 UTC, ZombineDev wrote:
>> Well, I agree, but I didn't say hard real-time, only 
>> performance requirements that are hard to achieve because the 
>> system is large, and becuase it would cost even more if the 
>> system was larger (slower).
>
> Yes, if you are writing for large scalable systems then it is 
> interesting to know what the ceiling is, but then you probably 
> also want something that is no worse than O(log N). Say for a 
> chat service you'd know that the more expensive to develop 
> solution can scale to 10 million users (O(1)), and the less 
> expensive do develop solution will become very expensive to run 
> when you hit 1 million (O(log N)).
>
> So Big-Oh can be useful when you work with very large sizes and 
> large variations, but in most cases I think it can be 
> misleading without a good description of the actual 
> implementation.
>
> Another very useful measure in real time is the amount of 
> variation between repeated calls. Say if there is a guarantee 
> of <50% variation, you can measure actual running time and add 
> 50% headroom on the hardware requirements. Some algorithms have 
> some fixed size tables they need to clear out every once in a 
> while and that can be very bad.

I strongly agree with what you said earlier that typical 
complexity analysis is a too naive model for real-world systems. 
Very often (e.g. due to the nature of real hardware) your time 
may be dominated by constants. Or a function which looks like 
O(1) is sometimes O(n), due to hidden complexity. This (the fact 
that constants matter) is especially true when you aim for O(1). 
And yes, variation of execution time is also very important.

However, here we're talking about API for containers and 
algorithms and I think that putting the complexity in the 
function signature is better than only using abstract data 
structures, because it makes you more aware of the consequences 
of your choice of data structures and algorithms that you make.
If we can figure out a way to put even more information it may be 
even better.