Previous Section
 < Free Open Study > 
Next Section


3.4 Comparison of Algorithms

As noted in this chapter, there is more than one way to solve most problems. If you were asked for directions to Joe's Diner (see Figure 3.8), you could give either of two equally correct answers:

  1. "Go east on the big highway to the Y'all Come Inn, and turn left."

  2. "Take the winding country road to Honeysuckle Lodge, and turn right."

Click To expand
Figure 3.8: Map to Joe's Diner

The two answers are not the same, but following either route gets the traveler to Joe's Diner. Thus both answers are functionally correct.

If the request for directions contained special requirements, one solution might be preferable to the other. For instance, "I'm late for dinner. What's the quickest route to Joe's Diner?" calls for the first answer, whereas "Is there a pretty road that I can take to get to Joe's Diner?" suggests the second. If no special requirements are known, the choice is a matter of personal preference-which road do you like better?

In this chapter, we have presented many algorithms. How we choose between two algorithms that perform the same task often depends on the requirements of a particular application. If no relevant requirements exist, the choice may be based on the programmer's own style.

Often the choice between algorithms comes down to a question of efficiency. Which one takes the least amount of computing time? Which one does the job with the least amount of work? We are talking here of the amount of work that the computer does. Later we also compare algorithms in terms of how much work the programmer does. (One is often minimized at the expense of the other.)

To compare the work done by competing algorithms, we must first define a set of objective measures that can be applied to each algorithm. The analysis of algorithms is an important area of theoretical computer science; in advanced courses, students undoubtedly see extensive work in this area. In this book, you learn about a small part of this topic, enough to let you determine which of two algorithms requires less work to accomplish a particular task.

How do programmers measure the work performed by two algorithms? The first solution that comes to mind is simply to code the algorithms and then compare the execution times for running the two programs. The one with the shorter execution time is clearly the better algorithm. Or is it? Using this technique, we can determine only that program A is more efficient than program B on a particular computer. Execution times are specific to a particular machine. Of course, we could test the algorithms on all possible computers, but we want a more general measure.

A second possibility is to count the number of instructions or statements executed. This measure, however, varies with the programming language used as well as with the individual programmer's style. To standardize this measure somewhat, we could count the number of passes through a critical loop in the algorithm. If each iteration involves a constant amount of work, this measure gives us a meaningful yardstick of efficiency.

Another idea is to isolate a particular operation fundamental to the algorithm and count the number of times that this operation is performed. Suppose, for example, that we are summing the elements in an integer list. To measure the amount of work required, we could count the integer addition operations. For a list of 100 elements, there are 99 addition operations. Note, however, that we do not actually have to count the number of addition operations; it is some function of the number of elements (N) in the list. Therefore, we can express the number of addition operations in terms of N: For a list of N elements, N - 1 addition operations are carried out. Now we can compare the algorithms for the general case, not just for a specific list size.

If we wanted to compare algorithms for multiplying two real matrices together, we could use a measure that combines the real multiplication and addition operations required for matrix multiplication. This example brings up an interesting consideration: Sometimes an operation so dominates the algorithm that the other operations fade into the background "noise." If we want to buy elephants and goldfish, for example, and we are considering two pet suppliers, we need to compare only the prices of elephants; the cost of the goldfish is trivial in comparison. Similarly, on many computers floatingpoint multiplication is so much more expensive than addition in terms of computer time that the addition operation is a trivial factor in the efficiency of the whole matrix multiplication algorithm; we might as well count only the multiplication operations and ignore the addition. In analyzing algorithms, we often can find one operation that dominates the algorithm, effectively relegating the others to the "noise" level.

Click To expand

Big-O

We have talked about work as a function of the size of the input to the operation (for instance, the number of elements in the list to be summed). We can express an approximation of this function using a mathematical notation called order of magnitude, or Big-O notation. (This is the letter O, not a zero.) The order of magnitude of a function is identified with the term in the function that increases fastest relative to the size of the problem. For instance, if

f(N) = N4 + 100N2 + 10N + 50

then f(N) is of order N4-or, in Big-O notation, O(N4). That is, for large values of N, some multiple of N4 dominates the function for sufficiently large values of N.

Big-O notation (order of magnitude) A notation that expresses computing time (complexity) as the term in a function that increases most rapidly relative to the size of a problem

Why can we just drop the low-order terms? Remember the elephants and goldfish that we discussed earlier? The price of the elephants was so much greater that we could just ignore the price of the goldfish. Similarly, for large values of N, N4 is so much larger than 50, 10N, or even 100N2 that we can ignore these other terms. This doesn't mean that the other terms do not contribute to the computing time, but rather that they are not significant in our approximation when N is "large."

What is this value N? N represents the size of the problem. Most of the rest of the problems in this book involve data structures-lists, stacks, queues, and trees. Each structure is composed of elements. We develop algorithms to add an element to the structure and to modify or delete an element from the structure. We can describe the work done by these operations in terms of N, where N is the number of elements in the structure. Yes, we know. We have called the number of elements on a list the length of the list. However, mathematicians talk in terms of N, so we use N for the length when we are comparing algorithms using Big-O notation.

Suppose that we want to write all the elements in a list into a file. How much work is involved? The answer depends on how many elements are in the list. Our algorithm is

If N is the number of elements in the list, the "time" required to do this task is

(N * time-to-write-one-element) + time-to-open-the-file

This algorithm is O(N) because the time required to perform the task is proportional to the number of elements (N)-plus a little time to open the file. How can we ignore the open time in determining the Big-O approximation? Assuming that the time necessary to open a file is constant, this part of the algorithm is our goldfish. If the list has only a few elements, the time needed to open the file may seem significant. For large values of N, however, writing the elements is an elephant in comparison with opening the file.

The order of magnitude of an algorithm does not tell you how long in microseconds the solution takes to run on your computer. Sometimes we need that kind of information. For instance, a word processor's requirements may state that the program must be able to spell-check a 50-page document (on a particular computer) in less than 120 seconds. For such information, we do not use Big-O analysis; we use other measurements. We can compare different implementations of a data structure by coding them and then running a test, recording the time on the computer's clock before and after the test. This kind of "benchmark" test tells us how long the operations take on a particular computer, using a particular compiler. The Big-O analysis, however, allows us to compare algorithms without reference to these factors.

Common Orders of Magnitude

O(1) is called bounded time. The amount of work is bounded by a constant and does not depend on the size of the problem. Assigning a value to the ith element in an array of N elements is O(l), because an element in an array can be accessed directly through its index. Although bounded time is often called constant time, the amount of work is not necessarily constant. Rather, it is bounded by a constant.

O(log2N) is called logarithmic time. The amount of work depends on the log of the size of the problem. Algorithms that successively cut the amount of data to be processed in half at each step typically fall into this category. Finding a value in a list of ordered elements using the binary search algorithm is O(log2N).

O(N) is called linear time. The amount of work is some constant times the size of the problem. Printing all the elements in a list of N elements is O(N). Searching for a particular value in a list of unordered elements is also O(N), because you (potentially) must search every element in the list to find it.

O(N log2N) is called (for lack of a better term) N log2N time. Algorithms of this type typically involve applying a logarithmic algorithm N times. The better sorting algorithms, such as Quicksort, Heapsort, and Mergesort discussed in Chapter 10, have N log2N complexity. That is, these algorithms can transform an unordered list into a sorted list in O(N log2N) time.

O(N2) is called quadratic time. Algorithms of this type typically involve applying a linear algorithm N times. Most simple sorting algorithms are O(N2) algorithms. (See Chapter 10.)

O(N3) is called cubic time. An example of an O(N3) algorithm is a routine that increments every element in a three-dimensional table of integers.

O(2N) is called exponential time. These algorithms are costly. As you can see in Table 3.3, exponential times increase dramatically in relation to the size of N. (Note that the values in the last column grow so quickly that the computation time required for problems of this order may exceed the estimated life span of the universe!)

Table 3.3: Comparison of Rates of Growth

N

log2N

N log2N

N2

N3

2N

1

0

1

1

1

2

2

1

2

4

8

4

4

2

8

16

64

16

8

3

24

64

512

256

16

4

64

256

4,096

65,536

32

5

160

1,024

32,768

4,294,967,296

64

6

384

4,096

262,114

About one month's worth of instructions on a super-computer

128

7

896

16,384

2,097,152

About 1012 times greater than the age of the universe in nanoseconds (for a 6-billion-year estimate)

256

8

2,048

65,536

16,777,216

Don't ask!

Throughout this discussion we have been talking about the amount of work the computer must do to execute an algorithm. This determination does not necessarily relate to the size of the algorithm, say, in lines of code. Consider the following two algorithms to initialize to zero every element in an N-element array:

Algorithm Init1

Algorithm Init2

items[0] = 0;
items[1] = 0;
items[2] = 0;
items[3] = 0;

items[N - 1] = 0;

for (index  = 0; index < N; index++)
   items[index] = 0;

Both algorithms are O(N), even though they greatly differ in the number of lines of code.

Now let's look at two different algorithms that calculate the sum of the integers from 1 to N. Algorithm Suml is a simple for loop that adds successive integers to keep a running total:

Algorithm Sum 1

sum = 0;
for (count = 1; count <= n; count++)
   sum = sum + count;

That seems simple enough. The second algorithm calculates the sum by using a formula. To understand the formula, consider the following calculation when N = 9:

  1 +  2 +  3 +  4 +  5 +  6 +  7 +  8 +  9
+ 9 +  8 +  7 +  6 +  5 +  4 +  3 +  2 +  1
-----------------------------------------------------------
 10 + 10 + 10 + 10 + 10 +-10 + 10 + 10 + 10  =  10 * 9 = 90

We pair up each number from 1 to N with another, such that each pair adds up to N + 1. There are N such pairs, giving us a total of (N + 1) * N. Now, because each number is included twice, we divide the product by 2. Using this formula, we can solve the problem: ((9 + 1 ) * 9)/2 = 45. Now we have a second algorithm:

Algorithm Sum2

sum = ((n + 1) * n) / 2;

Both of the algorithms are short pieces of code. Let's compare them using Big-O notation. The work done by Sum1 is a function of the magnitude of N; as N gets larger, the amount of work grows proportionally. If N is 50, Sum1 works 10 times as hard as when N is 5. Algorithm Sum1, therefore, is O(N).

To analyze Sum2, consider the cases when N = 5 and N = 50. They should take the same amount of time. In fact, whatever value we assign to N, the algorithm does the same amount of work to solve the problem. Algorithm Sum2, therefore, is O(1).

Is Sum2 always faster? Is it always a better choice than Sum1? That depends. Sum2 might seem to do more "work," because the formula involves multiplication and division, whereas Sum1 calculates a simple running total. In fact, for very small values of N, Sum2 actually might do more work than Sum1. (Of course, for very large values of N, Sum1 does a proportionally larger amount of work, whereas Sum2 stays the same.) So the choice between the algorithms depends in part on how they are used, for small or large values of N.

Another issue is the fact that Sum2 is not as obvious as Suml, and thus it is more difficult for the programmer (a human) to understand. Sometimes a more efficient solution to a problem is more complicated; we may save computer time at the expense of the programmer's time.

What's the verdict? As usual in the design of computer programs, there are tradeoffs. We must look at our program's requirements and then decide which solution is better. Throughout this text we examine different choices of algorithms and data structures. We compare them using Big-O, but we also examine the program's requirements and the "elegance" of the competing solutions. As programmers, we design software solutions with many factors in mind.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)