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.

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.

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

$2n-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.