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