Complexity nomenclature

[Ola Fosheim Grøstad via Digitalmars-d]

On Friday, 4 December 2015 at 10:35:33 UTC, ZombineDev wrote:
> 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.

Well, if the algorithm can choose between containers it might be 
interesting to query the characteristics of a set of operations 
on each container. Not sure if the method name is is the best way 
to do it. Although I guess having a generic find(x) and 
find_instantly(x) would be ok, if the latter verison basically 
means less than 200 cycles in all cases. If it means less than 
2000 cycles I think it is not so useful.

Maybe it is possible to make the inference as static analysis and 
in addition make it possible for libraries to express various 
guarantees. Since it is worst case it would be acceptable that if 
analysis fails it will result in "unbounded".