We need better documentation for functions with ranges and templates

[John Colvin via Digitalmars-d]

On Wednesday, 16 December 2015 at 23:00:03 UTC, Timon Gehr wrote:
> On 12/15/2015 12:26 PM, rumbu wrote:
>>
>> And personally, I found the MS remark more compact and more 
>> user
>> friendly than:
>>
>> "This is a best-effort implementation of length for any kind 
>> of range.
>> If hasLength!Range, simply returns range.length without 
>> checking upTo
>> (when specified). Otherwise, walks the range through its 
>> length and
>> returns the number of elements seen. Performes Ο(n) 
>> evaluations of
>> range.empty and range.popFront(), where n is the effective 
>> length of
>> range."
>>
>> Not everybody is licensed in computational complexity theory to
>> understand what O(n) means.
>
> One doesn't need to know any results or definitions from 
> complexity theory in order to understand what O(n) means. What 
> it means here is that for large enough n the actual number is 
> bounded from above by n multiplied by some unspecified constant.
> (In contexts like this, there is generally also an informal 
> assumption that the unspecified constants are reasonably small.)

Perhaps it's the physicist in me, but I like this way of thinking 
about it:

Given a running time R(n), the time-complexity is given by 
O(f(n)) iff df/dn = lim_{n -> inf} dR(n)/dn

Is that also a correct expression? Obviously I'm papering over 
the discretisation, but well, I did say physicist... :)