Comparing Algorithms

Algorithms can be compared on several criteria:

• Generality: can an algorithm be used with any data?
• Effectiveness: does an algorithm work?
• Termination: is an algorithm guaranteed to terminate?
• Efficiency: how much effort is taken when the algorithm is used?
• Elegance

We can use these criteria to compare searching algorithms and sorting algorithms.

Analysis of algorithms

To assess efficiency, we need to know how to analyse the computational complexity of the algorithm. The question to be answered is how many operations are required, for a given size of problem?

For searching and sorting:

• the "operations" involved are comparisons and exchanges.
• the "size of the problem" is the number of data items, generally denoted "N"

Several situations need to be considered:

• best case
• worst case
• average case
• average case when successful (for searching)

We are only interested in orders of magnitude, and the largest term.

• "big O" notation