0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The inner loop will only run $k$ times as you can see directly from the initial sequence you have written down. $\endgroup$ – M. Winter Jun 13 '18 at 6:18
  • $\begingroup$ 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? $\endgroup$ – laura Jun 13 '18 at 6:22
  • $\begingroup$ yes, $k+1$ of course! You are right. $\endgroup$ – M. Winter Jun 13 '18 at 6:24
  • $\begingroup$ @M.Winter ,outer loop is correct ..so final answer will be $2^{2^{k}} \times (k+1)$? $\endgroup$ – laura Jun 13 '18 at 6:26
  • $\begingroup$ 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})$. $\endgroup$ – M. Winter Jun 13 '18 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.