Is the time complexity of half array loop using two ifs is the same as full array loop using one if?

Question

I would like to know if the two variants of the code examples below technically have the same run-time complexity. For example (and for the sake of making a point, lets say the string's length is an even number): ``` //counting how many times char 'c' appear in the string s String s = "ascdwcccdweccaaa"; //the "array", contain char 'c' 6 times int counter = 0; //times char 'c' appear in the string for(int i=1; i <= s.length()/2; i++) { if(s.charAt(i-1) == 'c') counter++; if(s.charAt(s.length()-i) == 'c') counter++; } ``` Compared to this... ``` for(int i=0; i < s.length(); i++) if(s.charAt(i) == 'c') counter++; ``` The first example uses the index to check from both end and start of the array until it reaches the middle of the array (supposedly `O(n/2)` ) while the second example is strictly checking all chars in the array from start to end (supposedly `O(n)`) On the first example i need to use two `ifs`, while on the second example i need to use one `if`. Are these two codes technica…

Accepted Answer

Both of your programs have exactly the same `O(n)` complexity. In fact `O(n/2)` is equal to `O(n)` as it is the same order. But even taking that into account: you have two times less iterations performing two times more work. Total is the same.

So the programs have the same complexity. However the first one has several disadvantages:

it is more complex to read and less clear

what about arrays with odd number of elements?

JVM might do some fancy optimizations wrt. boundary checking (the VM might not check the boundaries all the time when it discovers you are simply iterating over the whole array). Using this fanciness might confuse the optimizer.

That being said you made your code harder to read, incorrect and presumably slower - while trying to optimize it.

Is the time complexity of half array loop using two ifs is the same as full array loop using one if?

Solution

Problem