Comparing time complexities

Question

Let's say we have an algorithm that goes through a list of n numbers twice and counts the number of the ones above 50 in one run and the ones below 50 in the other run and stores these in two variables. If we change it to do the same in one run by incrementing not just one but either of the variables in each step, do we change time complexity of the algorithm? Do we consider the new one faster?

I know it will require less steps but not exactly sure about time complexity notation.

EDIT:

Pseudocode 1:

for (i = 0; i < TOTAL_NUMBERS; i++) {
    if (numbers[i] >= 50) {
        greaterThan50++;
    }
}

for (i = 0; i < TOTAL_NUMBERS; i++) {
     if (numbers[i] < 50) {
        lessThan50++;
    }
}

Pseudocode 2:

for (i = 0; i < TOTAL_NUMBERS; i++) {
    if (numbers[i] >= 50) {
        greaterThan50++;
    }
    else {
        lessThan50++;
    }
}

Answer 1

Something is simple if you can obtain the same result but with smallest expression posible. So in this case if you combine the update of the two counters in the same loop the algorithm will need less CPU cycles to be executed. You can also save time in the number validation cause you can just make one if / else statement to do what you need.

A pseudocode could look like this:

for (i = 0; i < TOTAL_NUMBERS; i++) {
    if (numbers[i] >= 50) {
        greaterThan50 ++;
    }
    else {
        lessThan50 ++;
    }
}

If you want to exclude the numbers that are equal 50 you can do something like:

for (int i = 0; i < TOTAL_NUMBERS; i++) {
    if (numbers[i] > 50) {
        greaterThan50 ++;
    }
    else if (numbers[i] < 50) {
        lessThan50 ++;
    }
}

As you might notice in this last example you are doing an extra validation so it will take an extra step, but this algorithm will still be much faster than looping through the list twice (and also simpler since it requires less lines of code and makes the code more readable and easy to understand).

I hope this helps with your question :)

Answer 2

Big O notation is a general statement for how a measurement (execution time in your case) changes as input grows. The first takes twice as long to execute, but both versions execution times grow linearly with regard to input size, so they're both O(n) algorithms.

more reading here: http://en.wikipedia.org/wiki/Big_O_notation