algorithmbig-oexp

What is exp(O(n)) and how does it differ to O(exp(n))?

In a recent lecture, we were told that an algorithm has a time complexity of exp(O(n)), and that that was different to a time complexity of O(exp(n)). I am interested in the following:

  1. How do we read a time complexity of exp(O(n)) and what does it imply?
  2. What is the difference between an exp(O(n)) and O(exp(n)) time complexity?

I assume the first question will answer the second one as well, but an explicit answer would be very appreciated.

To clarify, the time complexities we were presented with were actually in Big-Theta, not Big-O, notation, but I assumed the same relevant properties would hold for both, and this would be a more useful way of phrasing the question (since I feel like people search for Big-O more than they do for Big-Theta).

For those who are curious, the algorithm in question is the brute-force method for finding a minimum cost path between nodes on a regular lattice. We were comparing it to a the much more efficient (Θ(n^2)) dynamic programming approach. The module I am taking is on computational biology, and the topic is global sequence matching for DNA and proteins.

Solution

  • I think the easiest way to understand what exp(O(n)) means is to demonstrate the difference:

    If we assume we are working in base e, then exp(O(n)) can be written as ef(n), where f(n) ∈ O(n). Notice that both n and 2n are O(n), however, when they are in the exponent, things are different: O(en) ≠ O(e2n), because O(e2n) = O((e2)n). The exponential expression has a different base, therefore belonging to a different class of functions.

    Thus, exp(O(n)) is a different class of functions than O(exp(n)), as the latter requires that the asymptotic growth follows that of en. (Naturally, if our base is something other than e, the same argument still applies.)

    An important result is that exp(O(n)) includes functions that grow faster than any function in O(exp(n)), and thus O(exp(n)) ⊆ exp(O(n)).

    What might be the source of the confusion is that exp(O(n)) is actually the same class as O(exp(O(n))). However, as exp(O(n)) is already a class of functions, there is no need to add the wrapping O. Because c·exp(f(n)) grows slower than exp(c·f(n)), thus c·exp(f(n)) ∈ exp(O(n)) for f(n) ∈ O(n).