CODEWITHSUNDEEP
javaalgorithmtime-complexitybig-o
Saad
Saad

Reputation: 907

Which one is faster?(from CTCI book)

I came across this two code snippets in CTCI book,

Code snippet 1:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE; 

for(int x : array) { 
    if (x < min) min = x;
    if (x > max) max = x;
}

Code snippet 2:

int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE; 

for(int x : array) { 
    if (x < min) min = x;
}

for(int x : array) {
    if (x > max) max = x;
}

The book didnt gave a clear cut answer on which one is faster and more efficient from assembly level and compiler optimization perspective. I believe both of this have O(n) running time. The first one has one loop with the expense of two conditional operations while the second one, loops twice with only one conditional operation.

To be technically precise the second run time would be O(2N) and the first one O(N) but since we omit the constants, both would be described as O(N). So let say for a huge size of N, would the constant really matter? Also which one would result in more optimized assembly code from a compiler perspective?

EDIT: The constants do no matter for a large size of N, but comparing the two code snippets, where one has a constant of 2, and the other one not, would it effect the running time, if we run both of them parallel on same size of N and same machine specs?

Upvotes: 4

Views: 234

Answers (2)

danbanica
danbanica

Reputation: 3038

Indeed, both code snippets have O(N) complexity.

You estimated the constants for the two code snippets as being 1 and 2, probably based on the number of the for instructions. However, this ignores the fact that the for in the first code snippet actually contains more instructions than the one in the second snippet. In general, finding tight Big-Oh constants is difficult, and it is an indirect approach for comparing the practical performance of two algorithms.

As mentioned in the comments, what will matter here would be memory accesses -- when using two fors it is possible to require to load the array into memory twice.

Assuming that we ignore these caching aspects -- a more direct approach than comparing complexity constants would be to directly look into the number of instructions made by each approach. The second snippet duplicates the instructions used for advancing through the array (e.g. incrementing the iterator), which makes it less efficient.

Upvotes: 0

Kedar Mhaswade
Kedar Mhaswade

Reputation: 4695

To be technically precise the second run time would be O(2N) and the first one O(N) but since we omit the constants, both would be described as O(N).

I don't think that is right. As far as the number of comparisons is concerned (and that is the essence here), in the first case, you are doing 2 comparisons per iteration, whereas in the second case there are two loops, but there is 1 comparison per iteration in each. So, these two are equivalent, since O(2N) = O(N) + O(N).

Of course, several correct comments reveal the practical aspects of running such a code in silico. The real reason we find the Big-Oh complexity of an algorithm is to get an idea of how the computation behaves without any regards to the computational (machine) power and in the presence of arbitrarily large N, the input size (that's why we say asymptotically).

Upvotes: 1

Related Questions