Before You Start
If an operation, such as inserting into a data structure, is \( \mathrm{O}(N) \), the cost of the operation grows no faster than \( f(n) = N \) for infinitely large values of \( N \).
Remember that we can compare the behavior of two functions for infinitely large inputs using \( \mathrm{o}, \mathrm{O}, \Theta, \Omega, \text{ and } \omega \).
A handy mnemonic to remember the order of the different class is “Charlie Chaplin jumping over a puddle under the full moon”:
In the Charlie Chaplin picture, the complexity symbols are ordered from top (strict upper bound) to bottom (strict lower bound):
- Little \( \mathrm{o} \), at the very top, is the full moon. It represents a strict upper bound on our function.
- Big \( \mathrm{O} \) is next. It's Charlie Chaplin's head, and represents a (not necessarily strict) upper bound on our function.
- Big \( \Theta \) is Charlie's body, and represents an upper and lower bound on our function.
- Big \( \Omega \) is Charlie's legs, and represents a (not necessarily strict) lower bound on our function.
- Little \( \omega \) is at the bottom, as the puddle that Charlie is jumping over. It represents a strict lower bound on our function.
(When logged in, completion status appears here.)