big-O and little-o

The definitions of big-O and little-o are quite similar, but little-o has an alternative definition in terms of taking a limit. In this post we explore building up a similar definition for big-O. We will be thinking of big-O and little-o from the perspective of asymptotic anaysis in computer science, so we don’t lose anything by assuming all or our functions are positve. Let’s start with the standard definitions of big-O and little-o. We say that, $f(n)$ is $O(g(n))$ or (by a slight abuse of notation) that $f(n) = O(g(n))$, if there exist positive constants $c$ and $n_0$, such that for all $n \geq n_0$, \[f(n) \leq cg(n)\] Contrast this with the definition of little-o,

$f(n) = o(g(n))$ if for all $c > 0$, there exist $n_0$, such that for all $n \geq n_0$, \[f(n) \leq cg(n)\]

The difference is that this inequality must hold for all $c$, so we can pick $c$ to be arbitrarily small (Note that in the definition of little-o, $n_0$ may depend on the choice of $c$). An equivalent definition of little-o is,

$f(n) = o(g(n))$ if

It is easy to see using the definition of limit that these two definitions of little-o are equivalent. This second definition is the one most often used for checking if $f(n)$ is $o(g(n))$, since we can apply the tools of calculus, including e.g. l’hospital’s rule, to calculate the limit instead of trying to find an $n_0$ for each $c$, which is usually more difficult. Do we have a similar definition for big-O? It may seem at first that the following is an equivalent to the one above, i.e. that a necessary and sufficient condition for $f(n)$ to be $O(g(n))$ is,

Unfortunately, this is not a valid definition of big-O. The problem is that the limit is not guaranteed to exist. This was not a problem in our definition of little-o, since if the limit is equal $0$ it must exit.

Here is an example of the trouble we could run into. Take $f(n)$ to be the function on the positive integers $\{0,1, \ldots, \}$ such that:

and let $g(n)=1$. Then the limit as $n \rightarrow \infty$ of $f(n)/g(n)$ does not exist. The function oscillates between $0$ and $1$ forever. On the other hand $f(n)$ is clearly $O(g(n))$, since

This demonstrates that if the definition of big-O is satisfied it may not be the case that the above limit exists. What about the other direction, i.e. if the limit exists, does this imply big-O, after all, we are usually trying to prove that some function is big-O of some other function. Let’s see, if the limit exists it is finite by definition, and hence equal to some constant $c$ so we have,

This means that there must be a $c$ and an $n_0$ such that, for all $n \geq n_0$

Voila, that’s the definition of big-O, so in fact if the limit exits then big-O is implied. That’s good, it means that if we can calculate the limit, then we can prove big-O and if the limit turns out to be zero then we have little-o as well. Still it would be nice to have a definition that worked even when the limit doesn’t exist like in our oscillating function from before.

$\limsup$ to the rescue

We need something more general than $\lim$, something that always exists. That’s where the $\limsup$ comes in. Unlike $\lim$, which must always be finite, we allow $\limsup$ to be $+\infty$. OK, so just what is the $\limsup$ otherwise known as the limit superior. Here is the formal definition,

Let’s take this piece by piece. First, what does $\sup$ mean in $sup_{j \geq n} h(j)$. Easy, $\sup$ means least upper bound. $\sup$ is similar to $\max$, so $\sup_{j \geq n} h(j)$ is like the maximum value of $h(j)$ on the set of all integers $j \geq n$. The reason we can’t use $\max$ is that it does not always exist, whereas the least upper bound ($\sup$) will always exist even if it is infinite.

For example suppose $h(n)$ is the function $1-2^{-n}$, $h$ has a horizontal asymptote at $y=1$. This function does not have a $max$, if you give me any number, say $c < 1$ I’ll give you an integer $j$ making $h(j)$ bigger, $c < h(j) < 1$. On the other hand $h(n)$ is always less than $1$ and there is no smaller number for which this is true, so $1$ is the $\sup_{n \geq 0} h(n)$. Nice, using $sup$ guarantees we don’t get into trouble with cases where the maximum is not attained.

Now that we understand what the supremum is, let’s replace the limit with it’s definition and see what it means for the $\limsup$ to be finite. If something is finite it must be equal some constant $c$. That is,

is equivalent to the statement that there exists a positive constant $n_0$ such that for all $n \geq n_0$,

observe that $sup_{j \geq n} h(j) \leq c$ is the same as saying that all values of $h(j)$ on the set of integers $\{j \geq n\}$ are less than $c$ – since if the $sup$ is less than $c$ all values are. Finally, we arrive at the statement, there exist positive constants $n_0$ and $c$ such that for all $n \geq N$,

I like to think of the $\limsup$ as saying that $h(n) \leq c$ eventually. All we have to do now is replace $h(n)$ with $f(n)/g(n)$ to arrive at

and we have the definition of big-O, proving that a finite $\limsup$ implies big-O. The proof in the other direction, i.e. that big-O implies that the $\limsup$ is finite is pretty much the same proof in reverse. Hence we have shown that the two definitions are equivalent! That is, an alternative definition of $f(n) = O(g(n))$ is

The only difference between this result and our naive guess is that we had to use $\limsup$ instead of $\lim$ to handle cases where the limit does not exist. By the way, when the limit exists it is equal to the $\limsup$. So we can summarize what we have so far by saying that if the $\limsup$ of $f/g$ is 0 then $f$ is $o(g)$, if it is finite but not zero $f$ is $O(g)$.