Complexity nomenclature
Walter Bright via Digitalmars-d
digitalmars-d at puremagic.com
Thu Dec 3 19:46:39 PST 2015
On 12/3/2015 5:27 PM, Andrei Alexandrescu wrote:
> 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!
Are you sure there are only 3 complexities? What if it's a self-balancing tree?
I'm also not sure it is a good idea to put the complexity in the name of the
primitive. Do any other algorithm libraries do that?
More information about the Digitalmars-d
mailing list