Time Complexity Analysis - Inner loop var gets squared

Question

j = 1
while (j < n) {
  k = 2
  while (k < n) {
    Sum += a[j]*b[k]
    k = k * k
  }
  j++
}

Answer 1

The increasing process of k = k*k is 2^{2^(t-1)}.

for example, the first k = 2

the second is 4

the third is 16 etc.

so in the loop k<n, the time it will process is 2^{2^(t-1)} <= n

so t = log(2,log(2,n)) + 1

and combining with the time j loops, the total time should be (n-1)(log(2,log(2,n)) + 1)

That is, overall, O(n log log n)

Answer 2

I almost agree with Jian Luan.

There are two while loops.

1.The outside is n times.

2.The inside depends on k. k=k*k from k=2. So 4=2*2, 16=4*4, 256=16*16...That is 2^(2^t)

2^(2^t) < n, So t = log(logn)

Totally, The O(n) is O(nloglog(n))

Jiajun Wang(Quentin)

Answer 3

The outside iteration is gonna take (n-1) times.

Then, the inside iteration:

The 1st time: k = 2 = 2^{2^0};

The 2nd time: k = 2² = 2^{2^1};

The 3rd time:k = 2^{4 =} 2^{2^2};

...

The Nth time k = 2^{2^(N-1)}.

If assume that the inner iteration is gonna take N times:

2^{2^(N-1)} < n => N < log(log n) +1;

So, the inner iteration is gonna take no more than log(log n) times.

The whole program is gonna take (n-1)*(log(log n) +1) = n*log(log n) + n - log(log n) -1 = O(n*log(log n));