# Calculating time complexity of function

## 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)}$$

• The inner loop will only run $k$ times as you can see directly from the initial sequence you have written down. – M. Winter Jun 13 '18 at 6:18
• yes you are right .As base are same ,comparing the exponents ,we can find that they too are in Geometric series.. $2^0,2^1,...2^k$ so number of terms =$k+1$ ..right? – laura Jun 13 '18 at 6:22
• yes, $k+1$ of course! You are right. – M. Winter Jun 13 '18 at 6:24
• @M.Winter ,outer loop is correct ..so final answer will be $2^{2^{k}} \times (k+1)$? – laura Jun 13 '18 at 6:26
• I think this is correct. For the asymptotic time complexity the +1 is not really important and I would write it as $\mathcal O(k2^{2^k})$. – M. Winter Jun 13 '18 at 8:59