CODEWITHSUNDEEP
loopstime-complexity
Malik Abdulaziz
Malik Abdulaziz

Reputation: 67

What should be the time complexity of the following loops?

Kindly check if the time complexities below are right or not.

Loop 1

for(int i =0; i*i < n; i+=2)

I think that the work done in this loop will be O(sqrt(n)) because I know that the condition will be met when i reaches sqrt(n). Also, incrementor (i +=2) will cause the result to complete in n/2 so overall work done will be sqrt(n)/2.

Loop 2

for(int i =0; i*i < n; i*=2)

I think that the work done in this loop will be O(log(n)) because the only thing that changed from previous question is the incrementor (i*=2) which will cause the loop to run in log(n) times. So overall work becomes log(sqrt(n)) which becomes O(log(n))

PS: If anyone has a cheat sheet of time complexities of various variants of loops or nested loops, kindly share it. Your help would be highly appreciated.

Upvotes: 1

Views: 146

Answers (1)

Jorge Verdeguer G&#243;mez
Jorge Verdeguer G&#243;mez

Reputation: 189

In the first case, you are correct for your assumptions. The time complexity would be O(sqrt(n)). We don't take into account the incrementor +=2 for calculating time complexity since we only take the highest magnitude modificator, in this case i*i < n.

In the second case, you would be right. However, take notice that the loop starts in i=0, and since the increment on this variable is done with i*=2 it will stay at value 0 forever, since 0*2 = 0.

Upvotes: 1

Related Questions