I am solving an algorithm question and my analysis is that it would run on O(2^sqrt(n)). How big is that? Does it equate to O(2^n)? Is it still non-polynomial time?

5

This is an interesting question. Fortunately, once you know how to solve it, it is not particularly hard.

For functions *f*: **N** → **R**^{+} and *g*: **N** → **R**^{+}, we have *f* ∈ **O**(*g*) if and only if lim sup_{n→∞} *f*(*n*) / *g*(*n*) ∈ **R**.

A function *f*: **N** → **R**^{+} has at most polynomial growth if and only if there exists a constant *k* ∈ **N** such that *f* ∈ **O**(*n* ↦ *n*^{k}). Let’s work this out for arbitrary but fixed *k* ∈ **N**.

lim sup_{n→∞} 2^{(n1/2)} / *n*^{k} =

lim_{n→∞} 2^{(n1/2)} / *n*^{k} =

lim_{n→∞} e^{log(2) n1/2} / e^{log(n) k} =

lim_{n→∞} e^{log(2) n1/2 − log(n) k} = ∞ ∉ **R**

The first equality is true because both, the nominator and the denominator, are monotonically growing steady functions. The second equality uses the identity *x*^{y} = e^{log(x) y}. The limit is not finite because the exponent in the final expression is not bounded above. Without giving a formal proof, it can be assumed to be known that *n*^{1/2} dominates log(*n*) asymptotically. Therefore, the function in question exceeds polynomial growth.

However, its growth is strictly less than exponential, where exponential is defined (by me, for this purpose) as **O**(*n* ↦ 2^{cn}) for *c* > 0. Showing this is even more straight forward.

lim sup_{n→∞} 2^{cn} / 2^{(n1/2)} = lim_{n→∞} 2^{cn − n1/2} = ∞ ∉ **R**

for any fixed *c* > 0. Therefore, the complexity of the function is somewhere truly in between polynomial and exponential.

How big is that? Well, O (2 ^ sqrt (n)) is exactly how big it is 🙁

To get an idea what it means, imagine your algorithm wouldn’t be just O (2 ^ sqrt (n)), but that it actually takes precisely 2 ^ sqrt (n) nanoseconds on your computer:

n = 100: 2^10 = 1024 nanoseconds. No time at all.

n = 1000: 2^31.xxx = 2 billion nanoseconds. Two seconds, that’s noticeable.

n = 10,000: 2^100 ≈ 10^30 nanoseconds = 10^21 seconds = 30 trillion years.

This is a *lot* better than 2^n nanoseconds, where n = 100 would take 30 trillion years, but still the size of problems that you can solve is quite limited. If you consider a problem “solvable” if your computer can solve it in one week, that’s about 6 x 10^14 nanoseconds, that’s about n = 2,400. On the other hand, up to n = 400 can be solved in a millisecond.

(In practice, for n = 10,000 both O (2 ^ sqrt (n)) and O (2 ^ n) take exactly the same time: Too long to wait for it. )

It does exceed any polynomial. Take another algorithm taking n^1000 seconds. Which is practically unsolvable for n = 2. This algorithm takes longer until n is about 885 million. But really, who cares? At that point the number of years that both algorithms take is a 9,000 digit number.