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 technically identical in their time-complexity? (given the fact i use two ifs when i only pass half the array in the first example, do they "even out"?)

Answer 1

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.

Answer 2

Besides your algorithm are not equivalent as your first fails for a length of 1 (1/2==0), when assuming every atomic operation has a uniform cost of 1, your first algorithm has the following complexity:

for (int i=1;                          // 1
    i <= s.length()/2;                 // 3 + ⎡n/2⎤ · ( 3
    i++) {                             //     1
    if(s.charAt(i) == 'c')             //     3
        counter++;                     //     1
    if(s.charAt(s.length()-i) == 'c')  //     4
        counter++;                     //     1
}                                      // )

The total uniform costs are 4 + ⎡n/2⎤·13 ≤ 14·⎡n/2⎤ for n ≥ 8. And since 14·⎡n/2⎤ ≤ 28·n and 28 is a constant factor, your algorithm is in Ο(n).

Or, as already said as a comment: n/2 · 2 is still equal to n.