Definition
Big-O Notation
Let
be functions. We say that is Big-O of , written if there exist constants
and such that for all , Limit Form
Assume that
for all sufficiently large . Then If the quotient has an ordinary limit, the
(limit superior) can be replaced by : a finite limiting ratio gives an eventual constant-factor bound.
Equality Misinterpretation
One often writes
This is standard shorthand, but it should not be read as ordinary equality. More precisely, Big O denotes a set of functions:
Thus
Example
Quadratic upper bound
Let
For all
, Hence
with and .
in exponent Warning