16 July 2013

A friend of mine, who is currently enrolled in the Algorithms course over at Coursera reached out to me with the following problem:

Assume two (positive) nondecreasing functions $f$ and $g$. If $f(n) = O(g(n))$, is it also true that $2^{f(n)} = O(2^{g(n)})$?

My friend felt unable to apply his understanding of big-O notation to this question. In fact, he felt tripped up by the $=$ signs in the above expression. I remembered being similarly at a loss a decade earlier doing my first Algorithms course at my alma mater, BITS Pilani, and I now realize that my confusion was at least partly due to bad notation. Computer Science-folks (as opposed to mathematicians), when teaching complexity, do not emphasize at all that big-O actually refers to a class, or a family of functions, rather than a single one:

$O(f(n))$ is the set of all functions whose absolute value (asymptotically) grows no faster than $\vert f(n) \vert$, by up to a constant factor.

Armed with the above informal definition, we (the mathematically trained) immediately see an abuse of notation in the above problem with:

and realize that the expression would be better written as

The belongs-to symbol ($\in$) is more appropriate than the equality symbol ($=$) since the left hand side is a single function, while the right hand side is a family of functions. In other words, we are making a statement about set membership. Unfortunately, this abuse of notation is widespread in Computer Science literature. Newcomers, as always, bear the brunt.

Before answering the original problem my friend posed, consider the more general problem:

Given two functions $f$ and $g$, if $f(n) \in O(g(n))$, is it also true that $2^{f(n)} \in O(2^{g(n)})$?

The answer is no, since $f(n) = -n$ and $g(n) = -n^2$ is a counterexample. Since $|-n| = |n|$ grows no faster than $|-n^2| = n^2$, we get that $f(n) \in O(g(n))$. But $|2^{-n}| = (0.5)^n$ does grow faster than $| 2^{-n^2} | = (0.5)^{n^2}$, and so $2^{f(n)} \notin O(2^{g(n)})$.

The nature of the counterexample however indicates to us that if we imposed the restriction that the functions were positive and non-decreasing, things might be different. In fact, if $x > 0$, $y > 0$, and $M > 0$, then $% $

In other words, yes, if $f$ and $g$ are positive, and $f(n) \in O(g(n))$, then $2^{f(n)} \in O(2^{g(n)})$.