Complexity nomenclature

[Andrei Alexandrescu via Digitalmars-d]

On 12/03/2015 09:24 PM, Timon Gehr wrote:
> On 12/04/2015 03:18 AM, Andrei Alexandrescu wrote:
>> On 12/03/2015 08:37 PM, Jack Stouffer wrote:
>>> On Friday, 4 December 2015 at 01:27:42 UTC, Andrei Alexandrescu wrote:
>>>> These complexities must be reflected in the name of the primitives.
>>>
>>> I don't see why. IMO, names should convey what the function does, not
>>> how it does it. Complexity is usually put in the function documentation
>>> in Phobos when it's not constant, especially for range based ones, I
>>> don't see a reason to change that.
>>
>> Complexity is part of the semantics, and in my design names and their
>> semantics go hand in hand. -- Andrei
>>
>
> Which is sensible. But in any given context, some parts of the semantics
> are usually abstracted away. Sometimes one wants to abstract over
> running times of called methods. ("This function calls this other
> function at most O(n) times.")

Sure, and there will be provision for that. The collections framework 
will contain logic such as: "If collection type C implements 
insertAfter, then implement UFCS function linearInsertAfter that 
forwards to it". So if as user you're fine with linearInsertAfter, it'll 
work as an upper bound. -- Andrei