Algorithm Analysis – Understanding Time Complexity of 2^sqrt(n)

algorithm-analysisbig o

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?

Best Answer

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^{(n^1/2)} / n^k =
lim_n→∞ 2^{(n^1/2)} / n^k =
lim_n→∞ e^{log(2) n^1/2} / e^{log(n) k} =
lim_n→∞ e^{log(2) n^1/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^{(n^1/2)} = lim_n→∞ 2^{cn − n^1/2} = ∞ ∉ R

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

Best Answer

Related Solutions

Algorithm Analysis – Space Complexity of Iterative Deepening DFS

Algorithm Analysis – How Meaningful Is Big-O Time Complexity?

Related Topic