Big-O Made Trivial

posted by Craig Gidney on September 3, 2013

In this post: Craig tries to convince you to treat asymptotic complexity as a relation, instead of like sets.

Awkward-O

Big-O notation is one of my pet peeves. It’s a perfect example of complicating something simple.

Even ignoring the fact that Big-O notation is hard to learn, because instead of looking like other notation it uses totally arbitrary symbols, it is clearly at odds with how people think about complexities. Have you ever seen someone write f = O(n) , as if a function could be equal to a set of functions, instead of $f \in O(n)$ ? How about O(n) = O(n^2) instead of $O(n) \subset O(n^2)$ ? I think the reason people write these (literally false) statements is because they’re thinking in terms of comparisons, whereas Big-O notation is formulated in terms of sets.

When a person writes O(n) = O(n^2) , they almost certainly didn’t intend to say “The set of functions asymptotically upper bounded by is the same as the set of functions asymptotically upper bounded by n^2 .”. That’s trivially false. They meant linear costs are asymptotically upper bounded by quadratic costs, but ended up misusing/abusing Big-O notation instead.

(I suppose I can’t actually speak for “people”, but personally I do think about asymptotic complexity as a relation.)

Given that we’re thinking of asymptotic complexity in terms of comparisons, why not use notation based on that?

Asymptotic Comparison Notation

So we want to represent asymptotic complexity as a relation. How does that work, exactly?

Well, we’ll use the same symbols we already use for relations and comparisons (, $\leq$ , , $\geq$ , and ) but slightly modify them to indicate asymptotic-ness. My personal (and arbitrary) preference is to indicate the asymptotic-ness by circling the operator. I represent “asymptotically less than” as $\Large \textcircled{\normalsize $\hspace{0.05 mm} <$}$ , “asymptotically equal to” as $\Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.05 mm} =$}} \normalsize$ , and so forth.

Here’s a table that shows each operator beside its English description, its analogue in Big-O notation, and its definition in terms of a proportional limit:

$\begin{tabular}{ l | l | l | l } \small Operator & \small English & \small Big-O & \small Limit Definition \\ \hline & & & \\ f \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize g & \text{\scriptsize Asymptotically Less Than} & f \in o(g) & \lim_{x \to \infty} \frac{f(x)}{g(x)} = 0 \\ & & & \\ f \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.05 mm} \leq$}} \normalsize g & \text{\scriptsize Asymptotically At Most} & f \in O(g) & \lim_{x \to \infty} \frac{f(x)}{g(x)} \in [0, \infty) \\ & & & \\ f \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.05 mm} =$}} \normalsize g & \text{\scriptsize Asymptotically Equal To} & f \in \Theta(g) & \lim_{x \to \infty} \frac{f(x)}{g(x)} \in (0, \infty) \\ & & & \\ f \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} \geq$}} \normalsize g & \text{\scriptsize Asymptotically At Least} & f \in \Omega(g) & \lim_{x \to \infty} \frac{f(x)}{g(x)} \in (0, \infty] \\ & & & \\ f \Large \textcircled{\normalsize $\hspace{0.1 mm} >$} \normalsize g & \text{\scriptsize Asymptotically More Than} & f \in \omega(g) & \lim_{x \to \infty} \frac{f(x)}{g(x)} = \infty \\ \end{tabular}$

Do you see how $\Large \textcircled{\normalsize $\hspace{0.05 mm} <$}$ has a definition that is the inverse of the definition of its inverse, $\Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} \geq$}} \normalsize$ ? How $\Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} \geq$}} \normalsize$ ‘s definition is equivalent to satisfying either $\Large \textcircled{\normalsize $\hspace{0.05 mm} >$}$ ‘s definition or $\Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} =$}} \normalsize$ ‘s definition (because it’s greater than OR equal)? How there’s no confusion about what’s lower bounding and what’s upper bounding due to the re-use of existing symbols?

Doesn’t that just… make sense?

Examples

Here’s a few examples of using the asymptotic comparison operators as well as their limit definitions:

Buying a computer with a faster processor doesn’t affect the complexity of an algorithm:
$f(x) \cdot c \hspace{1 mm} \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} =$}} \normalsize f(x)$ , where , because $\lim_{x \to \infty} \frac{f(x) \cdot c}{f(x)} = \lim_{x \to \infty} 1 \cdot c = c$ .
Linear algorithms are asymptotically less costly than quadratic algorithms:
$x \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize x^2$ because $\lim_{x \to \infty} \frac{x}{x^2} = \lim_{x \to \infty} \frac{1}{x} = \frac{1}{\infty} = 0$ .
Running two algorithms, one after the other, is at least as asymptotically expensive as one of them individually:
$f(x)+g(x) \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} \geq$}} \normalsize f(x)$ , where and are positive, because $\lim_{x \to \infty} \frac{f(x)+g(x)}{f(x)} = 1+\lim_{x \to \infty} \frac{g(x)}{f(x)} \geq 1 > 0$ .
Logarithmic algorithms are asymptotically less costly than polynomial algorithms (using L’Hôpital’s rule):
$lg(x) \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize x^c$ , for any , because $\lim_{x \to \infty} \frac{lg(x)}{x^c} = \lim_{x \to \infty} \frac{x^{-1}}{c \cdot x^{c-1}} = \lim_{x \to \infty} \frac{1}{c \cdot x^c} = \frac{1}{\infty} = 0$
Chaining:
$1 \hspace{1 mm} \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} =$}} \normalsize \hspace{1 mm} 2 \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} \alpha(x) \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} lg(x) \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} \sqrt{x} \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} x \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} x^\pi \hspace{1 mm} \Large \textcircled{\raisebox{1pt} {\normalsize $\hspace{0.1 mm} =$}} \normalsize \hspace{1 mm} x^\pi + x \hspace{1 mm} \Large \textcircled{\normalsize $\hspace{0.05 mm} <$} \normalsize \hspace{1 mm} \pi^x$

Summary

Comparison operators are a natural fit when thinking about asymptotic complexity. Personally, I use the existing comparison operators and circle them to indicate the comparison is asymptotic.

Discuss on Reddit

My Twitter: @CraigGidney

6 Responses to “Big-O Made Trivial”

Emperor XLII says:

September 3, 2013 at 11:28 pm

Unicode is with you 60% of the way: ?, ?, ?

CraigGidney says:

September 4, 2013 at 1:20 pm

What, and lose the fun of typing out “Large textcircled{normalsize $hspace{0.05 mm} <$} normalsize” every time?

(I did actually find those. The problem, besides the missing =, is that lots of unicode characters render inconsistently. In firefox I can see all three characters in your post. In chrome, two of them are replaced by squares. I didn’t want people seeing mis-rendered characters.)

tenpn says:

October 15, 2013 at 4:42 am

I’m in chrome on OSX and I can see all the characters. Since the job of the browser is to render unicode characters, I am surprised to find they can be inconsistent?

FF says:

September 7, 2013 at 8:10 am

Simple, elegant and smart, I might use it in the future to wow collegues. 😉

David Speyer says:

September 20, 2013 at 3:44 pm

I can see arguments for and against replacing = by subset , but the relation symbols you suggest are much less flexible than big O notation. For example, try writing cosh(O(1/n))^n = (1+O(1/n^2))^n = 1+O(1/n) in your preferred notation. When one side of the equation is nothing but a big O symbol, of course, you are right; the power comes when you need to embed the big O inside something else.

CraigGidney says:

September 20, 2013 at 4:57 pm

Yes, this was mentioned in the reddit discussion as well. The asymptotic relational operators are easier to learn and easier to use when they apply, but big-O is more extensible. For example, I particularly like the definition of polynomial time as P = n^O(1).

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Big-O Made Trivial