Search Algorithms and Efficiency

CSC 105 - The Digital Age - Weinman



Summary:
We discuss the general properties of algorithms and how they are expressed in computer programming languages.

Elements of Efficiency

Although computers are often considered to work very quickly, only some algorithms proceed rapidly; others take much longer. This 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.
For many purposes, it turns out that a high-level analysis provides adequate information to compare algorithms. For the most part, we will follow that approach.

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 Adapted from Run-Time Experiments