11

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?

  • 3
    Please do comment reason for down voting the question. Thanks! – Gaara Mar 12 '16 at 17:24
  • 4
    Honestly, I suspect people are mistaking this for an extremely trivial question, but it's not immediately obvious to me how to prove it either way, so I'll go write an answer and see if that changes people's minds. – Ixrec Mar 12 '16 at 17:38
  • 3
    Sub-exponential time, second definition, according to Wikipedia article (Disclaimer: I didn't downvote; and I don't know enough on this topic to say whether this is correct or not.) – rwong Mar 12 '16 at 17:44
  • 1
    Great! Subexponential time: "the running time of some algorithm may grow faster than any polynomial but is still significantly smaller than an exponential". This definitely answer my question and expands my knowledge on Big O analysis. Thanks a lot – Gaara Mar 12 '16 at 17:58
  • 1
    It is way less than O(2^n), especially for large numbers. Take an example of having a collection of 10 000 elements. 2^10000 is a number with about 3000 digits, that's how many cycles it would take to do an O(2^n) operation on it. With O(2^sqrt(n)) you're down to a number with 30 digits. The difference is extremely huge for large numbers in favour of the sqrt solution (for 1 milion elements that's (number with 300 000 digits)*cpu cycle versus (number with 300 digits)*cpu cycle). – Andy Mar 12 '16 at 20:07
16

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

For functions f: NR+ and g: NR+, we have fO(g) if and only if lim supn→∞ f(n) / g(n) ∈ R.

A function f: NR+ has at most polynomial growth if and only if there exists a constant kN such that fO(nnk). Let's work this out for arbitrary but fixed kN.

lim supn→∞ 2(n1/2) / nk =
limn→∞ 2(n1/2) / nk =
limn→∞ elog(2) n1/2 / elog(n) k =
limn→∞ elog(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 xy = elog(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 n1/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 ↦ 2cn) for c > 0. Showing this is even more straight forward.

lim supn→∞ 2cn / 2(n1/2) = limn→∞ 2cnn1/2 = ∞ ∉ R

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

6

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.