What is the asymptotic complexity of the following code snippet?

Question

for (i = 2; i < n; i = i * i) {
 for (j = 1; j < i / 2; j = j + 1) {
 sum = sum + 1;
 }
}

I know that the outer loop can run for a maximum of $n^2$ times and the inner loop will run for $\frac{n^2}{4}$ times.

• 喜欢算法和数学: Have you run your code for a few times? Can you print out sum at the end of the code? The printout will be the number of times the inner loop has been executed. Check whether it is expected, for example, when you set $n=10^6$.

Answer 1

The second loop runs in $O(i)$. The first loop goes over the powers 2ドル^{2^0}, 2^{2^1}, 2^{2^2}, \ldots$, until reaching $n$. So the overall running time is $$ O(2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m}), $$ where $m$ is the maximal integer such that 2ドル^{2^m} < n$. We can bound $$ 2^{2^0} + 2^{2^1} + 2^{2^2} + \cdots + 2^{2^m} \leq 2^1 + 2^2 + 2^3 + \cdots + 2^{2^m} \leq 2^{2^m+1} < 2n. $$ Therefore the overall running time is $O(n)$.

In fact, the same analysis gives the optimal bound $\Theta(2^{2^{\lfloor \log_2 \log_2 (n-1) \rfloor}})$, with a bit more work.

• Romantic Electron: Please edit the answer a bit.I didn't want to vote in negative.It's locked now, I can't undo it unless you edit it
• Yuval Filmus: @RomanticElectron Try now.

Answer 2

Since $i$ iterates in powers of 2ドル$ to reach a value $n$. The average complexity will be $log_{2}(n)$ only for outer loop.

But when $i$ = 2ドル$ ,its value will raise in terms of powers of 2ドル$ .The same will be true for inner loop iterations(Let's just ignore the divided by 2ドル$ factor since 2ドル$ is a constant). The total running time in terms of number of iterations of inner loop can be summed as

$i^1 + i^2 + i^3 + \cdots + i^{log_{2}(n)}$

OR

2ドル^1 + 2^2 + 2^3 + \cdots + 2^{log_{2}(n)}$.

But for any positive integer $x,$ 2ドル^1 + 2^2 + 2^3 + \cdots + 2^{x-1}= 2^{x}-2$. So the total number of steps will be

2ドル*2^{log_{2}(n)}-2$

Now because 2ドル^{log_{2}(n)}=n$ we can write the number of steps as

2ドルn-2$

Ignore all constants you get the complexity $O(n)$

Answer 3

You are asking for asymptotic complexity. O(n) is obviously an upper bound. However, for every epsilon there are plenty values of n that execute in less than n * epsilon steps, so that upper bound is quite useless. "N^2/4" is way off the mark. For example, for 257<= n<= 65536, there are only about 256 steps, far less than n.

Let f(n) = floor (log(log(n))), where log is the base 2 logarithm. Let g(x) = 2^(2^x)), then the asymptotic complexity is $\Theta(g(f(n))$

PS. Yuval is right, it’s floor(log(log(n-1)), not n.