Say if n here is any number less than 256 the inner loop is going to be true for 4 times, now what kind of sequence does the inner loop follow as n increases.
for ( int i=1; i<=n; i++){
for ( int j=2;j<=n; j=j*j){
}
}
The outer loop will be iterated n
times. The inner loop each time squared the previous value, i.e., 2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}
. Hence, the time complexity is n * k
. To compute the k
, we need to find a k
such that n = 2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k}
:
2 + 2^2 + 2^4 + 2^8 + ... + 2^{2^k} = sum_{t=0}^{k} 2^{2^t} = n
=> k = heta(log(log(n))
Therefore, the time complexity if Theta(n log(log(n)))
.