Extension: Intro to Asymptotic Notation

The word "asymptotics" originates with the concept of an asymptote: an asymptote of a curve is a line that the curve approaches but never touches.

Above, we see that the line $y=x$ is an asymptote for the curve $y = x - \frac{4}{x}$. For both very positive and very negative values of $x$, the curve looks almost exactly like the line.

In general, an asymptotic description of a function $f(x)$ tells us how quickly it grows for large $x$. Suppose that our favorite function is $f(x) = {x \choose 2} = \frac{x(x-1)}{2}$. Try to see if your intuition matches reality for the following comparisons:

Why would we want to think about functions this way? There are several reasons.

First, well-behaved functions can be grouped together into classes that grow about as quickly, and just knowing which class a function is in tells us a lot about it. For example, functions that grow exponentially (such as $2^x$ or $e^x$ or $1.01^x$) will always eventually become larger than functions that grow polynomially (such as $x^2$ or even $x^{100}$), if we take a sufficiently large value of $x$.

Second, by dropping "asymptotically irrelevant" information about a function, we might make it easier to work with. For example, for large values of $x$, a lot of what we need to know about $f(x) = 10x^2 + 3x + \frac12 \log x$ is captured if we approximate it by $x^2$; we will soon learn to write this as $f(x) \in O(x^2)$. Even less information is lost if we approximate $f(x)$ by $10 x^2$.

Third, sometimes we have no exact formula for a function, and the best we can do is an approximation. For example, the Prime Number Theorem tells us that the function $\pi(x)$, denoting the number of primes less than or equal to $x$, is approximately $\frac{x}{\ln x}$ when $x$ is large.

"Asymptotically" comparing two functions means that we consider only what $\lim _{x\to \infty}\frac{f(x)}{g(x)}$ instead of the specific values of $f(x), g(x)$.

Recall the $\mathcal{O}, \Omega, \Theta$ notation, we now state them in terms of limits:

Definition 1. We say $f(x)=\mathcal{O}(g(x))$ iff $\limsup_{x\to \infty}|\frac{f(x)}{g(x)}|<+\infty$.

Definition 2. We say $f(x)=\Omega (g(x))$ iff $\limsup_{x\to \infty}|\frac{f(x)}{g(x)}|>0$.

Definition 3. We say $f(x)=\Theta (g(x))$ iff $0<\limsup_{x\to \infty}|\frac{f(x)}{g(x)}|<+\infty$.

Also there's little-o notation:

Definition 4. We say $f(x)=o(g(x))$ iff $\lim_{x\to \infty}\frac{f(x)}{g(x)}=0$.

Note that in derivatives, we now have $f(x+h)-f(x)=f'(x)h+o(h)$.

Moreover, when $f(x),g(x)$ are both polynomials, $\limsup_{x\to \infty}|\frac{f(x)}{g(x)}|$ is determined by the degree of f and g as well as their highest coefficients, so it's enough to find their asymptotic behaviour by considering these terms. Check this yourself!