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... :)

On Wednesday, 16 December 2015 at 23:02:53 UTC, H. S. Teoh wrote:
> Any programmer that has any pretense of caring about the performance of their code ought to know what O(n) means. It's not that hard to understand. There are plenty of online resources to learn about this, even if you didn't have the privilege of having received formal computer science education.

Yes, just use the term "Worst case time complexity is O(n)".

A simple search on google for "time complexity" gives me a nice textual and graphical explanation.

On Monday, 14 December 2015 at 20:16:25 UTC, H. S. Teoh wrote:
> Imagine, for example, if the docs were to be formatted a little better, say something like this:
>
> 	bool isSameLength(Range1, Range2)
> 	                 (Range1 r1, Range2 r2)
> 		if (isInputRange!Range1 &&
> 		    isInputRange!Range2 &&
> 		    !isInfinite!Range1 &&
> 		    !isInfinite!Range2)
>
> The sig constraint block can be rendered in a different font / font size / color / whatever. The CT parameters similarly can be visually distinguished from the RT parameters.

That would be a great improvement.