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