Asymptotic Notation

Asymptotic Notation (Bachmann–Landau notation) is a notation for comparing the behavior of functions at extreme values – both very large, and very small. This is a convenient way to compare the performance of algorithms on large inputs, as well as the accuracy of approximations. This page will focus on the behavior at very large values, which is useful for analyzing the behavior of algorithms (both time and space requirements), rather than very minute values.

This notation is intended for functions that are always non-negative or, at least, tend towards a non-negative value.

Asymptotic Behavior

The asymptotic behavior of a function is its behavior as its input grows large.

\

For example, as x grows large, the three functions above all start to take on the same asymptotic behavior. Asymptotic notation gives a way to express the relationship between two functions' asymptotic behaviors.

Little-Oh

Suppose we have two functions f(x) and g(x), such that

$$\underset{x\to \infty }{lim}\frac{f\left(x\right)}{g\left(x\right)}=0$$

Then we say that $f\left(x\right)=o\left(g\right(x\left)\right)$ (spoken as "f is little oh of g"), which, colloquially, means that $g\left(x\right)$ grows much faster than $f\left(x\right)$ in the long run (i.e. for large values of $x$).

For example, consider $f\left(x\right)=x$ and $g\left(x\right)=x^2$. Because ${lim}_{x\to \infty }\frac{x}{x^2}=0$, we know $x=o\left(x^2\right)$. Therefore $x^2$ will not only eventually overtake $x$, and will become arbitrarily large relative to $x$. In other words, we can make $\frac{g\left(x\right)}{f\left(x\right)}$ (or $g\left(x\right)-f\left(x\right)$) become as large as we want by finding a sufficiently large $x$ value.

A Note on Notation

While the standard notation uses an equal sign (i.e. $f\left(x\right)=o\left(g\right(x\left)\right)$), a more precise notation might be $f\left(x\right)\in o\left(g\right(x\left)\right)$, where $o\left(g\right(x\left)\right)$ is the set of functions that are asymptotically dominated by $g\left(x\right)$. Nonetheless, using an equal sign is customary, and is the notation that will be used on this page.

Examples

This section contains examples of how one may determine the asymptotic relationship of two functions using L'Hôpital's Rule.

Example 1

Consider $f\left(x\right)=200x+10000$ and $g\left(x\right)=x^2$. Prove that $f\left(x\right)=o\left(g\right(x\left)\right)$.

From the graph, we can guess that $f\left(x\right)=o\left(g\right(x\left)\right)$, because (it appears) that for large values of $x$, $g\left(x\right)>f\left(x\right)$. To prove this, it suffices to prove that:

$$\underset{x\to \infty }{lim}\frac{f\left(x\right)}{g\left(x\right)}=limx\to \infty \frac{200x+10000}{x^2}=0$$

Using L'Hôpital's Rule, we have:

$$\underset{x\to \infty }{lim}\frac{200x+10000}{x^2}=\underset{x\to \infty }{lim}\frac{200}{2x}$$

Which is zero; therefore our original guess was correct, and $f\left(x\right)=o\left(g\right(x\left)\right)$.

Example 2

Let $f\left(x\right)=20x^2-10x+5$ and $g\left(x\right)=2x^2-x+10$.

From the graph, we can guess that $g\left(x\right)=o\left(f\right(x\left)\right)$. To verify this, we will again evaluate the limit with L'Hôpital's Rule:

$$\underset{x\to \infty }{lim}\frac{g\left(x\right)}{f\left(x\right)}=\underset{x\to \infty }{lim}\frac{2x^2-x+10}{20x^2-10x+5}=\underset{x\to \infty }{lim}\frac{4x-1}{40x-10}$$

Unlike the previous example, applying L'Hôpital's Rule doesn't seem to have reduced the fraction to an easily evaluable limit. Fortunately, we are welcome to apply L'Hôpital's Rule as many times as we like, without changing the value of the limit:

$$=\underset{x\to \infty }{lim}\frac{4}{40}=\frac{1}{10}$$

This is not zero, and so our guess was wrong: $f\left(x\right)$ is not dominated by $g\left(x\right)$. If we apply the same test but with $f\left(x\right)$ on top and $g\left(x\right)$ on the bottom to also verify that $g\left(x\right)\ne o\left(f\right(x\left)\right)$.

Properties of Little-Oh

An equivalent definition for $f\left(x\right)=o\left(g\right(x\left)\right)$ is:

$${\forall }_{c>0}{\exists }_{n>0}\text{such that}{\forall }_{x>n}c\cdot f\left(x\right)\le g\left(x\right)$$

In other words $g\left(x\right)$ will eventually overtake $f\left(x\right)$, no matter how much you scale $f\left(x\right)$ by. From our first example, we showed that $200x+10000=o\left(x^2\right)$. This means that, no matter what $c$ you pick, $c(200x+10000)$ will eventually be overtaken by $x^2$ – it's just a matter of finding a big enough $n$.

Little-oh has the following properties:

1. $f\left(x\right)=o\left(f\right(x\left)\right)$ is always false
2. $f\left(x\right)=o\left(g\right(x\left)\right)⟹g\left(x\right)\ne o\left(f\right(x\left)\right)$
3. $f\left(x\right)=o\left(g\right(x\left)\right)\text{and}g\left(x\right)=o\left(h\right(x\left)\right)⟹f\left(x\right)=o\left(h\right(x\left)\right)$
4. $f\left(x\right)=o\left(g\right(x\left)\right)⟹c+f\left(x\right)=o\left(g\right(x\left)\right)$
5. $f\left(x\right)=o\left(g\right(x\left)\right)⟹c\cdot f\left(x\right)=o\left(g\right(x\left)\right)$

The first three properties are essentially the same properties required of a strict ordering, which means that this notation gives us a way to order functions by how quickly they grow (see the "Common Functions" section). Indeed, little-oh is often thought of as a "less than" sign that compares functions via their asymptotic behavior.

The 4th and 5th properties show that asymptotic notation is independent of constant factors or shifts. This is useful in computer science, where such constants may vary by hardware, programming language, and other variables that are often hard to talk about precisely; asymptotic notation gives computer scientists a way to analyze algorithms independent of the hardware that is running it.

Common Functions

Functions that are frequently seen while analyzing algorithms are of particular use and interest. Because little-Oh notation suggests a strict ordering, the following functions are listed from smallest to largest, asymptotically.

1. $f\left(x\right)=1$
2. $f\left(x\right)=log\left(log\right(x\left)\right)$
3. $f\left(x\right)=log\left(x\right)$
4. $f\left(x\right)=x$
5. $f\left(x\right)=x\cdot log\left(x\right)$
6. $f\left(x\right)=x^{1+ϵ}$, $0<ϵ<1$
7. $f\left(x\right)=x^2$
8. $f\left(x\right)=x^3$
9. $f\left(x\right)=x^4$
10. ...
11. $f\left(x\right)=e^{cx}$
12. $f\left(x\right)=x!$

Theta, Omega, and Big-Oh

Theta and Little-Omega

Given that there exists notation for representing the relationship between two functions if ${lim}_{x\to \infty }\frac{f\left(x\right)}{g\left(x\right)}=0$, it seems natural to extend this notation to the other two cases: namely when the limit equals infinity, and when the limit equals a (positive) constant.

When $0<{lim}_{x\to \infty }\frac{f\left(x\right)}{g\left(x\right)}<\infty$, we say $f\left(x\right)=\Theta \left(g\right(x\left)\right)$ (pronounced "f is theta of g").

When ${lim}_{x\to \infty }\frac{f\left(x\right)}{g\left(x\right)}=\infty$, we say $f\left(x\right)=\omega \left(g\right(x\left)\right)$ (pronounced "f is little omega of g").

Little-omega is a natural complement to little-oh: if $f\left(x\right)=o\left(g\right(x\left)\right)$, then $g\left(x\right)=\omega \left(f\right(x\left)\right)$.

For any function $g\left(x\right)$, little-oh, little-omega, and Theta are disjoint sets. That is, $f\left(x\right)$ is either $o\left(g\right(x\left)\right)$, $\Theta \left(g\right(x\left)\right)$, or $\omega \left(g\right(x\left)\right)$, but cannot be more than one.

Big-Oh and Big-Omega

Though little-oh and little-omega offer a strict ordering, they are less used than their bigger siblings: big-oh and big-omega.

$f\left(x\right)=O\left(g\right(x\left)\right)$ if $f\left(x\right)=o\left(g\right(x\left)\right)$ or $f\left(x\right)=\Theta \left(g\right(x\left)\right)$, and, similarly, $f\left(x\right)=\Omega \left(g\right(x\left)\right)$ if $f\left(x\right)=\omega \left(g\right(x\left)\right)$ or $f\left(x\right)=\Theta \left(g\right(x\left)\right)$.

Use in Computer Science

In Computer Science, algorithms have runtimes, which are functions that take the size of their input and return (approximately) how long the algorithm will need to run. Big-Oh, in particular, sees widespread use, and it is standard practice that an algorithm's runtime be given using asymptotic notation.

For example, the algorithm mergesort (an algorithm that sorts a list of numbers) requires $\Theta \left(nlg\right(n\left)\right)$ time. This suggests that running the algorithm on a list with 1024 elements will take roughly 2.2 times longer than on a list with 512 elements.

In contrast, insertionsort (an algorithm that also sorts lists of numbers) runs in $\Theta \left(n^2\right)$ time. This suggests that bubble sort will run roughly 4 times longer on a list with 1024 elements than on a list with 512.

Here, we can use the simplified runtimes ($nlg\left(n\right)$ and $n^2$) to still make useful comparisons between the algorithms. In particular, as the size of the list gets large, we can expect the mergesort to eventually outperform insertionsort, because $nlg\left(n\right)=o\left(n^2\right)$.

Unfortunately, an algorithm's runtime often depends on more than just the size of the input, but on the particular flavor as well. For instance, some sorting algorithms behave very poorly on lists that are completely reserved (e.g. $[6,5,4,3,2,1]$) but very well on lists that are nearly sorted to begin with (e.g. $[1,2,3,4,6,5]$). Typically the worst-case (i.e. slowest) performance is used to determine the asymptotic behavior of the function. For instance, though bubble sort (another sorting algorithm) can run in $n$ time, in the worst-case scenario it requires $n^2$ time, though classifying it as an $O\left(n^2\right)$ algorithm.