CODEWITHSUNDEEP
loopstime-complexity
giorgioh
giorgioh

Reputation: 377

How many times is this nested while loop going to run?

I'm having trouble with this one, I know the inner loop will run log(n) in base 6. But the outer loop troubles me.

i=n
while i>2
   j=1
   while j<i
      j=j*2
      i=i/3

Upvotes: 0

Views: 109

Answers (1)

GZ0
GZ0

Reputation: 4268

The analysis is actually not as hard as you may think. Note that every time the inner loop is executed, the value of i decreases to a third of it. Hence for the entire loop to reach the exit condition i<=2, the inner loop needs to run \theta(log3(n)) times in total. That is the time complexity of the program. It is unnecessary to separately analyze how many times the outer loop runs and how many times the inner runs within each outer loop execution.

Upvotes: 1

Related Questions