Complexity nomenclature

[Idan Arye via Digitalmars-d]

On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu 
wrote:
> Consider the collections universe. So we have an imperative 
> primitive like:
>
> c.insertAfter(r, x)
>
> where c is a collection, r is a range previously extracted from 
> c, and x is a value convertible to collection's element type. 
> The expression imperatively inserts x in the collection right 
> after r.
>
> Now this primitive may have three complexities:
>
> * linear in the length of r (e.g. c is a singly-linked list)
>
> * linear in the number of elements after r in the collection 
> (e.g. c is an array)
>
> * constant (c is a doubly-linked list)
>
> These complexities must be reflected in the name of the 
> primitives. Or perhaps it's okay to conflate a couple of them. 
> I know names are something we're awfully good at discussing 
> :o). Destroy!
>
>
> Andrei

The complexities of the operations is a property of the data 
structure being used. If each collection type will have it's own 
set of method names based on the complexity of operations on it, 
we won't be able to have templated functions that operate on any 
kind of collection(or at the very least, these functions will be 
really tedious to code).