Asymptotic time complexity of a loop with x number of "if" statement vs asymptotic time complexity of x "if" statement with the loop in each

Question

I have problem at hand which can be solved in the following two ways.

   if(...) //First if statement
     for( i = 0; i < n; i++  ) //Loop over n elements
     { ... } //Some statement; Time Complexity O(1)

   if(...) //Second if statement
     for( i = 0; i < n; i++  ) //Loop over n elements
     { ... } //Some statement; Time Complexity O(1)

   if(...) //Third if statement
     for( i = 0; i < n; i++  ) //Loop over n elements
     { ... } //Some statement; Time Complexity O(1)

or by having 3 ifs in the same loop, like this..

   for( i = 0; i < n; i++  ) //Loop over n elements
     if(...) //First if statement
     { ... } //Some statement; Time Complexity O(1)
     if(...) //Second if statement
     { ... } //Some statement; Time Complexity O(1) 
     if(...) //Third if statement 
     { ... } //Some statement; Time Complexity O(1)

Now the asymptotic time complexity, should be same in both the cases O(3n) as the asymptotic time complexity of the loop is O(n) and asymptotic time complexity of each if statement is O(1).

So my question is, which is the better way to implement the solution and why ?

Please note, I am not concerned about the asymptotic space complexity.

In practice, It might depend on what you do inside those loops and how the compiler can rearrange statements. — WW., Jan 18 '16 at 11:43
It depends on what is done inside those loops. See http://stackoverflow.com/a/11227902/5781248 that tells about branch prediction. — J.J. Hakala, Jan 18 '16 at 11:46
In my case, each if statement removes some of the n elements depending upon whether they satisfy the if statement or not. But here I am looking for a more general answer, as in this case it can be argued that since each if removes some elements, number of items "n" might decreases with each loop. — KarateKid, Jan 18 '16 at 11:48
Well, it depends on your problem actually. If we're going to talk on your shared code; In the first method if all of the if statements get skipped you could save some time and resource. In second method it will go in a loop and iterate anyways. Vice versa, first method will run a for loop three times. Second method will only loop for once but actually will run if statements 300 times. Both has pros and cons. But I believe there is not much difference. But actually, those methods represents different problems to me. Not the same thing. — st., Jan 18 '16 at 11:50
@st. I am filtering out some of the elements based upon the if, hence these methods represents the same problem. In first case, element is added if it satisfies the flag condition to temporary array. In second case; each if sets a flag and the elements is filtered if all flags are true. So the final result is same the procedure. But as I said. I am looking for a more general answer, then this specific case. — KarateKid, Jan 18 '16 at 11:54
Of course, I guess I put it wrong way. There is no certain way to tell, before see your main logic. Any of these methods can make it better or worse. — st., Jan 18 '16 at 11:58

score 0 · Answer 1 · answered Jan 18 '16 at 11:57

First, we don't know the time complexity of the statement that will or will not be executed if the conditions are true. If it doesn't have constant time complexity, that will affect the time complexity of the whole construct. I'll assume it runs in constant time.

Second, the time complexity of the first version is not known. If all three conditions are false (and evaluated in constant time) then it is O (1). If one of the three conditions is true then it is O (n). Saying it is O (3n) is nonsense, because that's the same as O (n).

Third, if the conditions can be sometimes true and sometimes false during execution of the loop, then both versions are not comparable. If the order in which the loop statements are executed is relevant then both versions are not comparable. But if this is not the case, then a good compiler can transform version 2 into version 1 so the time complexity is the same.

Forth, if you want to know which one is faster you need to measure it.

Fifth, sixth, seventh, and eighth, if you want to know which one is faster you need to measure it.

Last, if you want to know which one is faster then you need to learn about caches, cache hierarchies, data locality, and how loops processing data are affected by them.

You are right that O(3n) = O(n), but since O(n) is the upper bound and not the average case. It will be wrong to the that the time complexity of the first version is not known. Also best case time complexity of 1 can if be achieved in the second case by simply writing an if statement like if () //Check if any of the 3 statenents are true else //Second case goes here — KarateKid, Jan 18 '16 at 12:07

Asymptotic time complexity of a loop with x number of "if" statement vs asymptotic time complexity of x "if" statement with the loop in each

1 Answers1