Is it really any different from O(2^n)??

It's like saying n where n is in the set of i/2 where i is any real number. If i is a set of real numbers, then n would be so as well and so O(2^n) is the same as O(2^(n/2)) right?

CodePudding user response：

2^(n/2) = √(2^n); also, lim 2^(n/2)/2^n = 0, so these two orders of complexity are quite different. In fact, they are much more different than n vs. n².

An example of O(2^n) cost is counting the ordered partitions of n 1 (e.g. n=3 -> (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) -> 8).

An example of O(2^(n/2)) cost is counting the ordered partitions of n 1 that are symmetric (e.g. n=3 -> (1,1,1,1), (1,2,1), (2,2), (4) -> 4).

CodePudding user response：

O(2^n) and O(2^(n/2)) are similar, but not identical. O(2^n) represents an algorithm whose time complexity is directly proportional to 2^n, while O(2^(n/2)) represents an algorithm whose time complexity is directly proportional to 2^(n/2). This means O(2^n) represents a problem that will double in size with each additional input, while O(2^(n/2)) represents a problem that will increase by a factor of 2^(1/2) with each additional input.

These complexities can be quite different in terms of the actual running time of the algorithm. For example, a problem of size 8 with O(2^n) is going to take 2^8 = 256 times more computation than the same problem with size 4, while O(2^(n/2)) will take 2^(8/2) = 16 times more computation. While both complexities are exponential, the actual running time can be very different.

In general, O(2^n) is considered to be much worse than O(2^(n/2)), as it increases much faster. So, it's important to understand the difference between these complexities, and not confuse them with each other.