Why use comparisons instead of runtime for comparing two algorithms?

Question

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. Why can't we compare which one is better by running both programs and counting the total time needed to run the algorithms?

Answer 1

This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure runtimes. For learning something about the algorithm, don't do it.

Let me first give some reasons why using runtimes is not a good idea.

1. Generality
   Runtimes measured using one language and one compiler on one machine have little meaning if you change any component. Even slightly different implementations of the same algorithm may perform differently because you trigger some compiler opimisation in on case but not in the other.
2. Prediction
   So you have a couple of runtimes for some inputs. What does that tell about the runtime of some other input? In general, nothing.
3. Significance
   Usually, you won't benchmark all inputs (of some size), so that immediately restricts your ability to compare algorithms: maybe your test set triggered the worst case in one and the best case in the other algorithm? Or maybe your inputs were too small to exhibit the runtime behaviour.
4. Metering
   Measuring runtimes well is not trivial. Is there a JIT? Has there been contention, i.e. are you counting time the algorithm did not even run? Can you reproduce exactly the same machine state for another run (of the other algorithm), in particular concurrent processes and caches? How is memory latency dealt with?

I hope these convinced you that runtimes are a horrible measure to compare algorithms, and that some general, abstract method for investigating algorithm runtime is needed.

On to the second part of the question. Why do we use comparisons or similar elementary operations?

1. Analytic tractability
   Assuming you want to do formal analysis, you have to be able to do it. Counting individual statements is very technical, sometimes even hard; some people do it nevertheless (e.g. Knuth). Counting only some statements -- those that dominate the runtime -- is easier. For the same reason, we often "only" investigate (upper bounds on) worst-case runtime.

2. Dominance
   The selected operation dominates the runtime. That does not mean that it contributes the most runtime -- comparisons clearly do not, e.g. in Quicksort when sorting word-sized integers. But they are executed the most often, so by counting them you count how often the most executed parts of the algorithm are run. Consequently, your asymptotic runtime is proportional to the number of dominant elementary operations. This is why we are comfortable using Landau notation and the word "runtime" even though we only count comparisons.

Note that it can be useful to count more than one operation. For example, some Quicksort variants take more comparisons but less swaps than others (on average).

For what it's worth, after you have done all the theory you might want to revisit runtimes in order to verify that the predictions your theory makes are sound. If they are not, your theory is not useful (in practice) and has to be extended. Memory hierarchy is one of the first things you realise is important but missing in basic analyses.

Answer 2

This is because the total time to run the algorithms has a dependency on the hardware in which it is ran on along with other factors. It is not reliable to compare two algorithms if one is running on a Pentium 4 and the other running on, let's say, a Core i7. Not only this, but let's say you ran both on the same computer. What's to say that they both have the same amount of processor time? What happens if some other process has a higher priority than the process of the one of the algorithms?

To get past this, we decouple away from this overall time to complete, and instead comparing based on how well the algorithm scales. You may have noticed notation such as O(1) or O(n^2) in the research papers. This may require a bit more reading, if you are interested see Big O notation.

Answer 3

Since the other answers explain why we analyze runtime in terms of number of elementary operations, let me offer a couple of reasons for why comparisons are the right metric of many (not all) sorting algorithms:

• for many sorting algorithms the number of comparisons dominates the running time, i.e. at least as many comparisons are performed as any other elementary operation
• comparisons are the expensive operation; think about how a sorting routine is implemented in library: the sort function is passed an array of elements and a pointer to a function that compares two elements; in general calling and waiting for the compare function to execute is more expensive than "internal" operations; as this function is provided by the user, it's harder to optimize it
• (this may or may not be a good reason for some) we can can say something interesting about the number of comparisons that are sufficient and necessary to sort a sequence; we know how to do this in the worst case and on average for various distributions, even how to design an algorithm that converges to optimal as it is run on items sampled iid from an unknown distribution (Self-Improving Algorithms); we know how to do this when some comparisons are given for free (Sorting with Partial Information)