Calculating time complexity of function

125 Views Asked by At

Question

Although my question seems to be a computer science question, still I am posting it here because I think this question requires me to solve a series (Geometric series).

Consider the following code snippet and find its time complexity:


int main()

{

$n=2^{2^{k}}$

for(i=1;i<=n;i++)

{

  j=2;
  while(j<=n)
    {
     j=j^{2}
    }
}

}

My Approach

Inner lop will run by keeping the value of $j$ as

$$2^1,2^2,2^4,\dots,2^{2^{k}}$$

now

number of times inner loop will run=$\log 2^{2^{k}}=2^k$

Hence total number of times entire program will run

$$2^{2^{k}} \text{(for outer loop)}\times 2^k\text{(for inner loop)}$$

Please help me if I am making a mistake