5 ms·
I always found the mathematical definitions of asymptotic notation the most clear: An algorithm with runtime r(n) is "big O" of f(n) if the limit as n -> infin
by gamegoblin 13y ago
I always found the mathematical definitions of asymptotic notation the most clear:
An algorithm with runtime r(n) is "big O" of f(n) if the limit as n -> infinity of r(n) / f(n) <= some constant.
EDIT: See replies below.
- teraflop 13y agoAlmost; r(n) doesn't have to have that property, but it must be bounded above by a function that does have that property. For instance, consider the function r(n) = x*(sin(x)+1).
- krcz 13y agoOr one can use lim sup.
- conistonwater 13y agoThis is wrong; in the definition it should be "<= some constant", and it should ideally also mention that r and f need to positive, or else take absolute values of them. As an example of a bug in your definition, consider "sin(n) = O(1)". Also, if you say "r(n)/f(n) <= constant", then you don't need to take the limit as "n -> infty", and can talk about "all n".
- fdej 13y ago> I always found the mathematical definitions of asymptotic notation the most clear Which definition of asymptotic notation is there besides the mathematical definition, which by definition defines it? :)