How to calculate time complexity for this algorithm

Question

Compute the complexity of the following Algorithm.

i = 1;
while(i < n+1)
{
   j=1
   while(j < n+1) 
   {
      j = j*2
   }
   i++
}

No. *You* compute the complexity of the following Algorithm. — PeeHaa, Jul 15 '15 at 07:51
would it not be nice if one could post your homework here like that? we can call it getyourhomeworkdone.com but youwontlearnanything.net — Shane_Yo, Jul 15 '15 at 08:01
It is not homework.It's sample question..and i dont want the direct answer.My question was how to calculate it.. — Waqas Malik, Jul 15 '15 at 08:06
Yeah i follow and thats why i thanks to him for giving some hints. — Waqas Malik, Jul 15 '15 at 08:08
Could you figure it out? Consider accepting my answer if it helped solving your question. — adrianus, Jul 19 '15 at 09:09

score 0 · Accepted Answer · edited May 23 '17 at 10:24

0

Ask yourself, in which way does i ~~increment~~ grow towards the final value n? How many times will the outer loop run for a given n?

The same for the inner loop. I recommend you read through somthing like this or this SO post and maybe start with some examples:

n = 100;
i = 1;
while (i < n+1){
    j = 1;
    while (j < n+1) {
        j = j*2
    }
    i = i+1;
}

How many times exactly will both of the loops run?

edited May 23 '17 at 10:24

Community

answered Jul 15 '15 at 07:57

adrianus

That were some hints already. Read through the link provided or do your own google search with `time complexity of nested loops` and tutorials will pop up everywhere (even for your exact problem). – adrianus Jul 15 '15 at 08:02

1 Answers1