Extension: Intro to Little-o Notation

The set $o(1)$ (read as "little-o of 1")

In the introduction to asymptotics, we said that the asymptotic behavior of a function $f(x)$ tells us about what happens to $f(x)$ when $x$ is large. We will begin, then, by talking about expressions that become almost entirely irrelevant for large values of $x$.

What should we consider irrelevant? We could pick a threshold such as $\epsilon = 0.001$, and saying that quantities smaller than $\epsilon$ don't matter to us. But this is problematic for a few reasons.

First, arbitrary constants aren't elegant, and are defeated by simple things such as changing units. We don't want our definition of "irrelevant" to depend on whether we use kilometers or centimeters to measure length.

Second, we run into problems when dealing with multiple expressions. The quantities $0.0006$ and $0.0008$ are each smaller than the threshold $\epsilon$ we chose; but their sum, $0.0014$, exceeds $\epsilon$, so suddenly it matters to us. We'd like to be able to entirely forget about "irrelevant" quantities, and we can't do that here.

Instead, we make the following definition: Let $o(1)$ be the set of functions $f(x)$, such that for any threshold $\epsilon > 0$, we have $|f(x)| < \epsilon$ for all large enough $x$.

What does "large enough" mean? It usually depends on $\epsilon$: the smaller the threshold, the further you'll have to go until $f(x)$ becomes that small. Formally, there should be a function $X(\epsilon)$, such that if $x > X(\epsilon)$, then the bound $|f(x)| < \epsilon$ holds.

The functions in $o(1)$ will be the ones that we'll ignore in our asymptotic analysis.

Let's play around with this definition.

Consider $f(x) = x + \frac 4x$. For large $x$, the first term here is much more important than the second: in fact, $f(x) - x \in o(1)$ by our definition. This makes $x$ a good asymptotic description of $x + \frac4x$.

If we think of $a + S$ as denoting the set $\{a + s : s \in S\}$, when $S$ is a set, we can also write this description as $f(x) \in x + o(1)$. This is a concise way of saying "$f(x)$ is basically $x$, plus an error that becomes insignificant when $x$ is large".

General little-o notation

Generalizing the notion of $o(1)$, we define $o(g(x))$ to be the set of functions $f(x)$ such that, for any threshold $\epsilon > 0$, we eventually have $|f(x)| < \epsilon \cdot g(x)$ if we take $x$ to be large enough. The intuitive meaning of this definition is that $o(g(x))$ is the set of functions that are irrelevant compared to $g(x)$.

For example, take the function $f(x) = \frac{x(x-1)}{2}$ (which counts the number of pairs that can be picked from a set of $x$ objects). For large $x$, $f(x)$ can be approximated fairly well by $\frac{x^2}{2}$, but the difference between them is $\frac{x}{2}$, which is still pretty big. We could write, however, that $$f(x) = \frac{x^2}{2} + o(x^2).$$ Relative to $x^2$, the error in this approximation is small, as $x$ becomes large.

Asymptotics at a point

Although most of the time, we consider the asymptotics of a function $f(x)$ for large $x$, we could instead look at how $x$ behaves close to some specific point. For example, we can talk about $o_{x \to 0}(x)$: the set of functions $f(x)$ that are insignificant compared to $x$, as long as $x$ is sufficiently close to $0$.

As before, we want to choose a threshold $\epsilon > 0$. We say that $f(x) \in o_{x \to a}(g(x))$ if $|f(x)| < \epsilon \cdot g(x)$ for all $x$ "sufficiently close to $a$". How do we make this last bit precise? Depending on $\epsilon$, we might need "sufficiently close" to mean different things: it could mean "between $a - 0.1$ and $a+0.1$" or "between $a - 0.0001$ and $a + 0.0001$". Formally, we choose a radius $\delta$, usually depending on $\epsilon$, such that as long as $a - \delta < x < a + \delta$, we have what we want: $|f(x)| < \epsilon \cdot g(x)$.

A popular approximation in physics, for instance, is that $\sin \theta \in \theta + o_{\theta \to 0}(\theta)$. For sufficiently small angles $\theta$, we can approximate $\sin \theta$ by the angle $\theta$ itself (in radians).