# What is the asymptotic complexity of the following code snippet?

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$. Feb 12 '19 at 2:00

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.

• 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 Mar 14 '19 at 17:07
• @RomanticElectron Try now. Mar 14 '19 at 17:08

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

$$2n-2$$

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

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.