Comparison-based Algorithms

  • Define what is meant by "comparison-based algorithms."

Lower bounds prove that we cannot hope for a better algorithm, no matter how hard we try!

When we study lower bounds, we often do so in restricted models of computation, that specify what types of operations may be performed on the input (and at what cost).

A lower bound in a restricted model means the only hope for improvement is to somehow do something outside the model.

For example, all sorting algorithms we studied sort an input array by comparing pairs of elements and moving elements around based on the results of these comparisons.

Those algorithms can be used to sort any (generic) type of data as long as they are comparable. (In Java, that means the data must implement the Comparable interface.)

All searching/sorting algorithms that we have seen so far use only comparisons to gain information about the input. We call these algorithms, comparison-based.

A comparison-based algorithm is an algorithm where the behavior of the algorithm is based only on the comparisons between elements.

The lower bound on the runtime of a comparison-based algorithm is the total number of comparisons needed to solve the problem, in the worst case (or in the expected case for randomized algorithms).

We will prove the lower bound on the total number of comparisons performed by comparison-based searching/sorting algorithms are $\Omega(\lg n)$ and $\Omega(n \lg n)$, respectively.

We will also see we can do better than $\Omega(n \lg n)$ for sorting when we don't restrict the algorithm to a comparison-based model.