Big-O is to little-o as =
is to <
. Big-O is an inclusive upper bound, while little-o is a strict upper bound.
For example, the function f(n) = 3n
is:
O(n²)
, o(n²)
, and O(n)
O(lg n)
, o(lg n)
, or o(n)
Analogously, the number 1
is:
= 2
, < 2
, and = 1
= 0
, < 0
, or < 1
Here's a table, showing the general idea:
(Note: the table is a good guide but its limit definition should be in terms of the superior limit instead of the normal limit. For example, 3 + (n mod 2)
oscillates between 3 and 4 forever. It's in O(1)
despite not having a normal limit, because it still has a lim sup
: 4.)
I recommend memorizing how the Big-O notation converts to asymptotic comparisons. The comparisons are easier to remember, but less flexible because you can't say things like nO(1) = P.