CODEWITHSUNDEEP
performancealgorithm
ArM
ArM

Reputation: 307

Why is comparison usually considered the Basic Operation while evaluating algorithm efficiency?

I'm currently getting to know various rudimentary algorithms (sort, search, etc.), and I find that most books talk about calculating the efficiencies of said algorithms (O(n logn), etc.).

While calculating these, some authors usually call comparison as the Basic Operation (most expensive), and then calculate how many of these occur for the whole algorithm, and then finally give an asymptotic notation for it.

For example, for the brute force Selection Sort, this is the algorithm I see on Wikipedia:

int i,j;
int iMin;

for (j = 0; j < n-1; j++) {
    iMin = j;
    for ( i = j+1; i < n; i++) {
        if (a[i] < a[iMin])
            iMin = i;
    }

    if(iMin != j)
        swap(a[j], a[iMin]);
}

This is what is said about the analysis of its efficiency:

Selection sort is not difficult to analyze compared to other sorting algorithms since none of the loops depend on the data in the array. Selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n − 1 elements and so on, for (n − 1) + (n − 2) + ... + 2 + 1 = n(n − 1) / 2 ∈ Θ(n^2) comparisons (see arithmetic progression). Each of these scans requires one swap for n − 1 elements (the final element is already in place).

Correct me if I'm wrong, but it seems to me that the comparison a[i] < a[iMin] is being considered as the most expensive operation here.

Why not the comparisons and increments in the for loop headers, and the swap operation?

P.S.: I know there are hundreds of questions on this site about what each of the asymptotic notations mean/stand for, but that's not what I'm asking about. I also know there are more efficient algorithms to sort, but that's also not what I'm asking about.

Upvotes: 1

Views: 539

Answers (1)

Seth Battin
Seth Battin

Reputation: 2851

The loops and other code-infrastructure of implementing the algorithm is proportional to the number of comparisons. Roughly, for each iteration of the loop, a comparison will be made. The swap operation will happen in some other proportion to the comparisons, and require some other quantity of work per item. In effect, this means the actual count of machine instructions per comparison is greater than the effort of the comparison itself. However, that is not the important part of big-O notation.

The whole purpose is to describe the rate of growth between two different input sizes. It doesn't matter if work per item is two instructions per comparison or four instructions. If the algorithm is O(n^2) and your input n is 100, that makes the difference 20000 to 40000. If input is 1000, it's 2000000 to 4000000. Compare that to O(n*Log(n)), which would be (2 * 3 * 1000) versus (4 * 3 * 1000). Obviously, the important part is the number of zeros, not the leading numeral.

In other words, you can solve your problem of 2 versus 4 by buying a computer that is twice as fast. You cannot resolve the differences between algorithms that way. There will always be some coefficient of computational work required to implement the algorithms. Don't worry about that; worry about how often that work must be executed.

Upvotes: 3

Related Questions