On Thursday, 17 December 2015 at 00:06:05 UTC, John Colvin wrote:
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... :)
That's how I think about it usually, but I think it's more
general than just analyzing run-times of programs. You could use
big O notation to classify any kind of function (wikipedia has a
more mathematical definition).
