ÒOÓ Notation
lÒOÓ
is letter ÒOhÓ (for ÒorderÓ)
lUsed
to express upper bounds on running time (number
of steps)
lT ë O(f)
means that
($c)("n) T(n) < c f(n)
($c)("n) T(n) < c f(n)
lThink
of O(f) as the set of functions that grow no faster than a constant times the value of f.
lThis
is Òbig-OhÓ; Òlittle-ohÓ has a different meaning.
l