Search Algorithms and Efficiency

CSC 105 - The Digital Age - Weinman



Summary:
We discuss how to measure the efficiency of an algorithm before studying the particular problem of searching.

Elements of Efficiency

Although computers are often considered to work very quickly, only some algorithms proceed rapidly; others take much longer. This accompanying laboratory exercise provides an intuitive framework for the consideration of algorithm effectiveness, including the amount of time and memory required for an algorithm. When algorithms are applied to successively larger data sets, some algorithms may scale up nicely while others require more time than may be feasible. Also, when several algorithms are available to solve a problem, it is natural to wonder if one solution is better than another. Altogether, we might use many criteria to evaluate such solutions, including:

Accuracy:

Of course, any program should produce correct answers. (If we were satisfied with wrong results, it is trivial to produce many such answers very quickly.) However, it may not be immediately clear just how accurate results should be in a specific instance. For example, one algorithm may be simple to program and may run quickly, but it only may be accurate to 5 decimal places. A second algorithm may be more complex and much slower, but may give 15 place accuracy. If 5-place accuracy is adequate for a specific application, the first algorithm is the better choice. However, if 10 or 12 place accuracy is required, the slower algorithm must be used.

Efficiency:

Efficiency can be measured in many ways: programmer time, algorithm execution time, memory used, and so on. If a program is to be used once, then programmer time may be a major consideration, and a simple algorithm might be preferred. If a program is to be used many times, however, then it may be worth spending more development time with a complex algorithm, so the procedure will run very quickly.

Use of Memory:

One algorithm may require more computer memory in which to execute. If space (i.e., memory) is a scarce resource, then the amount of space an algorithm requires should be taken into consideration when comparing algorithms.

Ease of Modification:

It is common practice to modify old programs to solve new problems. A very obscure algorithm that is difficult to understand, therefore, is usually less desirable than one which can be easily read and modified.
For the accompanying laboratory exercise, we focus on algorithm execution time.

Algorithm Execution "Time"

In determining algorithm execution time, we may proceed in several ways: Each of these approaches has advantages, but each also has drawbacks. Execution times on a specific machine normally depend upon details of the machine and on the specific data used. Timings may vary from data set to data set and from machine to machine, so experiments from one machine and one data set may not be very helpful in general.
As you will soon learn, different machines support different instructions, trading off programming complexity for hardware complexity (and energy use). For example, some machines may use only a single command to multiply two numbers in memory and store the result, while other machines may take several instructions to accomplish the task. As a result, measure of execution time by counting the number of instructions it takes to run an algorithm on a particular machine may tell us more about that machine than the general algorithm.
For many purposes, it turns out that a high-level analysis provides adequate information to compare algorithms. In the abstract, we do not really care whether a multiplication takes one instruction or three, because this difference is an uninformative constant factor. For the most part, we will follow that approach. In effect, we count the number of abstract, simple "steps" (additions, comparisons, reads, writes, etc.) it takes to run an algorithm on a data set of a given size.

Acknowledgments

Created: Henry Walker, December 31, 2003.
Revised: Henry Walker, February 27, 2006
Marge Coahran, March 14, 2007
Marge Coahran, April 3, 2008
Jerod Weinman, January 2, 2009.
Jerod Weinman, January 8, 2014.
Adapted from Run-Time Experiments