Asymptotics

We need to measure the behavior of a function $f(n)$ as $n$ grows larger. Here is where asymptotic notation comes to the rescue.

We have already seen a simple asymptotic equivalence example in the previous section to show that $(n^2 + n)$ and $n^2$ are asymptotically equivalent, denoted as $(n^2 + n) \sim n^2$. The limit of their quotient goes to $1$, and that's how we determined it.

If a function $f$ is asymptotically smaller than a function $g$, then $f(n)$ is equal to the little oh of $g(x)$:

That means, the limit of their quotient should go to $0$ as $x$ approaches infinity:

For example, $1000x^{1.9}$ is asymptotically smaller than $x^2$.

Simplifying $\frac{1000x^{1.9}}{x^2}$, we get $\frac{1000}{x^{0.1}}$.

And, as $x$ approaches infinity, the whole thing approaches $0$:

Given that $a$ and $b$ are nonnegative numbers,

Let's see.

$b - a \gt 0$ because of the given definitions: they are nonnegative and $a \lt b$.
Therefore, as $x$ approaches infinity, $\frac{1}{x^{b - a}}$ will approach $0$. That means, $x^a$ is little oh of $x^b$.

The star of this show is the big oh notation, which is used to measure the upper bound on the growth of a function. In other words, it is to measure the worst-case scenario. If a function $f$ is big oh of a function $g$, that is, $f(x) = O(g(x))$, it means that the limit of their quotient as $x$ approaches infinity is finite. Let $f$ and $g$ be positive, if $\lim_{n \to \infty} \frac{f(x)}{g(x)}$ exists*, then:

An example is that $3n^2 = O(n^2)$:

$3$ is definitely less than infinity, it is indeed true that $3n^2 = O(n^2)$.

The definition generally used is with limit superior:

Also, note that with big oh, constant factors don't really matter.

*Definition taken from Criterion 2 (Finite limit of ratio implies Big Oh).

When two functions $f$ and $g$ have the same order of growth, we can use theta: $f = \Theta(g)$.
It means that, $f = O(g)$ and $g = O(f)$.
It's an equivalence relation.

One thing to keep in mind with big oh is that it defines a relation between the growth rates of two functions, not a quantity.
That's why writing it like $O(g) = f$ is risky.

Let's look at an example.
Obviously, $x = O(x)$, and usually with symmetry, we are supposed to be able to write it as $O(x) = x$ as well.
But, $2x$ also has the same upper bound, that is, $2x = O(x)$.
Now, we just wrote that $O(x) = x$, by that reasoning, it must also be that $2x = x$. But, that is certainly false!

So, we can't say something like "a function $f$ is at least $O(n^2)$", because $O(n^2)$ is not a quantity, it is a relation.

• previous
• next