3.2 Comparing Algorithms

3.2.1 Introduction

How do you compare two algorithms for solving some problem in terms of efficiency? We could implement both algorithms as computer programs and then run them on a suitable range of inputs, measuring how much of the resources in question each program uses. This approach is often unsatisfactory for four reasons. First, there is the effort involved in programming and testing two algorithms when at best you want to keep only one. Second, when empirically comparing two algorithms there is always the chance that one of the programs was “better written” than the other, and therefore the relative qualities of the underlying algorithms are not truly represented by their implementations. This can easily occur when the programmer has a bias regarding the algorithms. Third, the choice of empirical test cases might unfairly favor one algorithm. Fourth, you could find that even the better of the two algorithms does not fall within your resource budget. In that case you must begin the entire process again with yet another program implementing a new algorithm. But, how would you know if any algorithm can meet the resource budget? Perhaps the problem is simply too difficult for any implementation to be within budget.

These problems can often be avoided by using asymptotic analysis. Asymptotic analysis measures the efficiency of an algorithm, or its implementation as a program, as the input size becomes large. It is actually an estimating technique and does not tell us anything about the relative merits of two programs where one is always “slightly faster” than the other. However, asymptotic analysis has proved useful to computer scientists who must determine if a particular algorithm is worth considering for implementation.

The critical resource for a program is most often its running time. However, you cannot pay attention to running time alone. You must also be concerned with other factors such as the space required to run the program (both main memory and disk space). Typically you will analyze the time required for an algorithm (or the instantiation of an algorithm in the form of a program), and the space required for a data structure.

Many factors affect the running time of a program. Some relate to the environment in which the program is compiled and run. Such factors include the speed of the computer’s CPU, bus, and peripheral hardware. Competition with other users for the computer’s (or the network’s) resources can make a program slow to a crawl. The programming language and the quality of code generated by a particular compiler can have a significant effect. The “coding efficiency” of the programmer who converts the algorithm to a program can have a tremendous impact as well.

If you need to get a program working within time and space constraints on a particular computer, all of these factors can be relevant. Yet, none of these factors address the differences between two algorithms or data structures. To be fair, if you want to compare two programs derived from two algorithms for solving the same problem, they should both be compiled with the same compiler and run on the same computer under the same conditions. As much as possible, the same amount of care should be taken in the programming effort devoted to each program to make the implementations “equally efficient”. In this sense, all of the factors mentioned above should cancel out of the comparison because they apply to both algorithms equally.

If you truly wish to understand the running time of an algorithm, there are other factors that are more appropriate to consider than machine speed, programming language, compiler, and so forth. Ideally we would measure the running time of the algorithm under standard benchmark conditions. However, we have no way to calculate the running time reliably other than to run an implementation of the algorithm on some computer. The only alternative is to use some other measure as a surrogate for running time.

3.2.2 Basic Operations and Input Size

Of primary consideration when estimating an algorithm’s performance is the number of basic operations required by the algorithm to process an input of a certain size. The terms “basic operations” and “size” are both rather vague and depend on the algorithm being analyzed. Size is often the number of inputs processed. For example, when comparing sorting algorithms the size of the problem is typically measured by the number of records to be sorted. A basic operation must have the property that its time to complete does not depend on the particular values of its operands. Adding or comparing two integer variables are examples of basic operations in most programming languages. Summing the contents of an array containing nn integers is not, because the cost depends on the value of nn (i.e., the size of the input).

Example: Largest value in an array

Consider a simple algorithm to solve the problem of finding the largest value in an array of nn integers. The algorithm looks at each integer in turn, saving the position of the largest value seen so far. This algorithm is called the largest-value sequential search and is illustrated by the following function:

// Return position of largest value in integer array A
function largest(A):
    currlarge = 0                 // Position of largest element seen.
    for i = 1 to A.size():     // For each element,
        if A[currlarge] < A[i]:   // if A[i] is larger,
            currlarge = i         // remember its position.
    return currlarge              // Return largest position

Here, the size of the problem is A.size(), the number of integers stored in array A. The basic operation is to compare an integer’s value to that of the largest value seen so far. It is reasonable to assume that it takes a fixed amount of time to do one such comparison, regardless of the value of the two integers or their positions in the array.

Because the most important factor affecting running time is normally size of the input, for a given input size nn we often express the time 𝐓\mathbf{T} to run the algorithm as a function of nn, written as 𝐓(n)\mathbf{T}(n). We will always assume 𝐓(n)\mathbf{T}(n) is a non-negative value.

Let us call cc the amount of time required to compare two integers in function largest. We do not care right now what the precise value of cc might be. Nor are we concerned with the time required to increment variable ii because this must be done for each value in the array, or the time for the actual assignment when a larger value is found, or the little bit of extra time taken to initialize currlarge. We just want a reasonable approximation for the time taken to execute the algorithm. The total time to run largest is therefore approximately cncn, because we must make nn comparisons, with each comparison costing cc time. We say that function largest (and by extension, the largest-value sequential search algorithm for any typical implementation) has a running time expressed by the equation

𝐓(n)=cn \mathbf{T}(n) = cn

This equation describes the growth rate for the running time of the largest-value sequential search algorithm.

Example: Accessing the first array value

The running time of a statement that assigns the first value of an integer array to a variable is simply the time required to copy the value of the first array value. We can assume this assignment takes a constant amount of time regardless of the value. Let us call c1c_1 the amount of time necessary to copy an integer. No matter how large the array on a typical computer (given reasonable conditions for memory and array size), the time to copy the value from the first position of the array is always c1c_1. Thus, the equation for this algorithm is simply

𝐓(n)=c1 \mathbf{T}(n) = c_1

indicating that the size of the input nn has no effect on the running time. This is called a constant running time.

Example: Nested for-loop

Consider the following code:

sum = 0
for i = 0 to n-1:
    for j = 0 to n-1:
        sum = sum + 1

What is the running time for this code fragment? Clearly it takes longer to run when nn is larger. The basic operation in this example is the increment operation for variable sum. We can assume that incrementing takes constant time; call this time c2c_2. (We can ignore the time required to initialize sum, and to increment the loop counters i and j. In practice, these costs can safely be bundled into time c2c_2.) The total number of increment operations is n2n^2. Thus, we say that the running time is 𝐓(n)=c2n2\mathbf{T}(n) = c_2 n^2.

3.2.3 Growth Rates

The growth rate for an algorithm is the rate at which the cost of the algorithm grows as the size of its input grows. The following figure shows a graph for six equations, each meant to describe the running time for a particular program or algorithm. A variety of growth rates that are representative of typical algorithms are shown.

Two views of a graph illustrating the growth rates for six equations. The bottom view shows in detail the lower-left portion of the top view. The horizontal axis represents input size. The vertical axis can represent time, space, or any other measure of cost.

The two equations labeled 10n10n and 20n20n are graphed by straight lines. A growth rate of cncn (for cc any positive constant) is often referred to as a linear growth rate or running time. This means that as the value of nn grows, the running time of the algorithm grows in the same proportion. Doubling the value of nn roughly doubles the running time. An algorithm whose running-time equation has a highest-order term containing a factor of n2n^2 is said to have a quadratic growth rate. In the figure, the line labeled 2n22n^2 represents a quadratic growth rate. The line labeled 2n2^n represents an exponential growth rate. This name comes from the fact that nn appears in the exponent. The line labeled n!n! also grows exponentially.

As you can see from the figure, the difference between an algorithm whose running time has cost 𝐓(n)=10n\mathbf{T}(n) = 10n and another with cost 𝐓(n)=2n2\mathbf{T}(n) = 2n^2 becomes tremendous as nn grows. For n>5n > 5, the algorithm with running time 𝐓(n)=2n2\mathbf{T}(n) = 2n^2 is already much slower. This is despite the fact that 10n10n has a greater constant factor than 2n22n^2. Comparing the two curves marked 20n20n and 2n22n^2 shows that changing the constant factor for one of the equations only shifts the point at which the two curves cross. For n>10n>10, the algorithm with cost 𝐓(n)=2n2\mathbf{T}(n) = 2n^2 is slower than the algorithm with cost 𝐓(n)=20n\mathbf{T}(n) = 20n. This graph also shows that the equation 𝐓(n)=5nlogn\mathbf{T}(n) = 5 n \log n grows somewhat more quickly than both 𝐓(n)=10n\mathbf{T}(n) = 10 n and 𝐓(n)=20n\mathbf{T}(n) = 20 n, but not nearly so quickly as the equation 𝐓(n)=2n2\mathbf{T}(n) = 2n^2. For constants a,b>1,naa, b > 1, n^a grows faster than either logbn\log^b n or lognb\log n^b. Finally, algorithms with cost 𝐓(n)=2n\mathbf{T}(n) = 2^n or 𝐓(n)=n!\mathbf{T}(n) = n! are prohibitively expensive for even modest values of nn. Note that for constants a,b1,ana, b \geq 1, a^n grows faster than nbn^b.

We can get some further insight into relative growth rates for various algorithms from the following table. Most of the growth rates that appear in typical algorithms are shown, along with some representative input sizes. Once again, we see that the growth rate has a tremendous effect on the resources consumed by an algorithm.

Table: Growth rates

This table shows costs for representative growth rates.

n loglogn\log\log n logn\log n nn nlognn \log n n2n^2 n3n^3 2n2^n
1616 22 44 242^{4} 424=264 \cdot 2^{4 = 2^{6}} 282^{8} 2122^{12} 2162^{16}
256256 33 88 282^{8} 828=2118 \cdot 2^{8 = 2^{11}} 2162^{16} 2242^{24} 22562^{256}
10241024 3.3\approx 3.3 1010 2102^{10} 1021021310 \cdot 2^{10 \approx 2^{13}} 2202^{20} 2302^{30} 210242^{1024}
64K64K 44 1616 2162^{16} 16216=22016 \cdot 2^{16 = 2^{20}} 2322^{32} 2482^{48} 264K2^{64K}
1M1M 4.3\approx 4.3 2020 2202^{20} 2022022420 \cdot 2^{20 \approx 2^{24}} 2402^{40} 2602^{60} 21M2^{1M}
1G1G 4.9\approx 4.9 3030 2302^{30} 3023023530 \cdot 2^{30 \approx 2^{35}} 2602^{60} 2902^{90} 21G2^{1G}

3.2.4 Growth Rates Ordering Exercise