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