The Whole Asymptotic Family
So why is it called Big \( \mathrm{O} \)? It looks like a pretty regular sized \( \mathrm{O} \) to me!
Aha! You have the eye of a detective! It's called Big \( \mathrm{O} \) because there is also a Little \( \mathrm{o} \)!
Whaaaaaaaaat?!
We've talked about \( \mathrm{O} \), which means "no worse than" or "as bad as or better than." There is also an \( \mathrm{o} \), which means "definitely better than."
Similarly, \( \Omega \) means "no better than" or "as good as or worse than", and there is also an \( \omega \) (that's a lower-case omega), which means "definitely worse than."
All of these symbols are relationships between functions. It can be helpful to think of them as analogous to numeric relationships (like \( < \) or \( > \)), but they aren't literally the same. For functions, rather than comparing numerical values, we are typically comparing orders of complexity. But the analogy can really help you reason about how asymptotic symbols work.
So here is the whole family:
Asymptotic Notation | In Words | Sort of like… |
Some people remember the order of the asymptotic complexity "family" with this visualization, which we like to think of as "Charlie Chaplin jumping over a puddle under the full moon:"
\( \mathrm{o} \) and \( \omega \) are fairly obscure; we won't need them much in this course. But it's good to know they exist! Not being aware of them is like knowing about ≤ but not <.
Usually we are trying to get the tightest bound that we can!
Saying \( f(n) \in \mathrm{o}(g(n)) \) is kind of like saying "It definitely takes less than 7 hours to get from Claremont to LA."
Like… it's true but it's rarely useful to tell somebody that.
(When logged in, completion status appears here.)