CS 70

The Whole Asymptotic Family

  • Dog speaking

    So why is it called Big \( \mathrm{O} \)? It looks like a pretty regular sized \( \mathrm{O} \) to me!

  • LHS Cow speaking

    Aha! You have the eye of a detective! It's called Big \( \mathrm{O} \) because there is also a Little \( \mathrm{o} \)!

  • Dog speaking

    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…
\( f(n) \in \mathrm{o}(g(n)) \) \( f(n) \) is definitely better than \( g(n) \) \( x < y \)
\( f(n) \in \mathrm{O}(g(n)) \) \( f(n) \) is no worse than \( g(n) \) \( x \leq y \)
\( f(n) \in \Theta(g(n)) \) \( f(n) \) is similar to \( g(n) \) \( x = y \)
\( f(n) \in \Omega(g(n)) \) \( f(n) \) is no better than \( g(n) \) \( x \geq y \)
\( f(n) \in \omega(g(n)) \) \( f(n) \) is definitely worse than \( g(n) \) \( x < y \)

Say that we have a function \( f(n) = n^2 + 4n - 6 \). Which of the following are true? (Use the analogy to numerical comparisons to figure it out!)

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:"

  • LHS Cow speaking

    \( \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 <.

  • RHS Cow speaking

    Usually we are trying to get the tightest bound that we can!

  • LHS Cow speaking

    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."

  • RHS Cow speaking

    Like… it's true but it's rarely useful to tell somebody that.

(When logged in, completion status appears here.)