-1

I am trying to find the time complexity of simultaneous loops, and I am stuck up on this question.

Find the time complexity of this simultaneous loop

  for(int i=1,int j=0; i*i<=n && j<=n ;j=j*2 ,i++);

Can someone explain how to approach these types of questions?

Satyam Katiyar
  • 3
  • 3
  • Does this answer your question? [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) – Robert Harvey Dec 13 '20 at 14:27
  • `for(int i=1,int j=0;…` will not compile. Perhaps you meant `for (int i=1, j=0;…`. But then `j` will never change, since `j=j*2` will only set it to zero. So perhaps you meant `for (int i=1, j=1;…`? Or maybe `i` was supposed to be doubled and `j` was supposed to be incremented? You will need to correct and clarify the problem. – Eric Postpischil Dec 13 '20 at 14:44
  • In any case, in this situation, the code is simply bound by whichever condition reaches its limit first. So the complexity analysis proceeds figuring out which one that is and then by using that condition alone and ignoring the other one. – Eric Postpischil Dec 13 '20 at 14:51
  • Is there any more code involved? – Nico Haase Dec 14 '20 at 20:07

1 Answers1

0

Variable "i" is increased by 1 and stops at sqrt(n). Variable "j" is increased by two multiplied every step, but its initial value is zero, so it can not break the loop. So "i" variable reached to the end when n limits to a big number.

For complexity calculations, we focus the power of n or logarithmic of n values. Scalar values are not important. We discard 1, 2 or 10 steps. So the complexity of your statement is O(sqrt(n)). Initial values do not affect the complexity of statements.

Ismail Durmaz
  • 2,521
  • 1
  • 6
  • 19
  • 1
    The code in the question appears to be mistaken, since `j` never takes any value other than zero. If the grammatical error in `for(int i=1,int j=0;…` is corrected by removing the `int`, this answer is correct that the order is sqrt(n), but for the wrong reason. Were it not for the error in handling `j`, the logarithmic case would bound execution, and the order would be log(n). For example, if n were 10,000 and `j` were started at 1, there would be 100 steps until `i*i` reached 10,000 but only 14 steps until `j` exceeded it. – Eric Postpischil Dec 13 '20 at 14:47
  • You are right, I didn't pay attention j's initial value. j variable can not break the loop. I think, O(sqrt(n)) is more preferable than O(log). https://stackoverflow.com/a/42038665/13106495 – Ismail Durmaz Dec 13 '20 at 14:55
  • 1
    Declare `i` and `j` before the loop (so they survive after the loop), initialize `j` to 1, and add code after the loop to show which value reached its limit. You will find `j` reaches the limit first except for n < 49. `i*i` will go through values 1, 4, 9, 16, 25, 36, 49, 64, 81, 100,…, while `j` will go through 1, 2, 4, 8, 16, 32, 64, 128, 256, 512,… – Eric Postpischil Dec 13 '20 at 15:08
  • Yes, I have tested with many "n" values, "j" is faster reached to the end for large numbers. I was wrong. Thank you, Eric Postpischil – Ismail Durmaz Dec 13 '20 at 15:32