We need better documentation for functions with ranges and templates

[Timon Gehr via Digitalmars-d]

On 12/17/2015 01:06 AM, John Colvin wrote:
>>
>> 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

I would just say that R(n) is (in) O(f(n)). ('Complexity' does not even 
imply that the statement that follows talks about asymptotics.)

> is given by  O(f(n)) iff

(Note that O(f(n)) is an upper bound.)

> df/dn = lim_{n -> inf} dR(n)/dn
>
> Is that also a correct expression?

What this is saying is that for large n, R is approximately a linear 
polynomial and that f is a linear polynomial with the limiting slope. In 
particular, 2·n is not in O(n) with this definition and O(n²) is empty.

Probably the intended meaning was different.

> Obviously I'm papering over the
> discretisation, but well, I did say physicist... :)