## 1.3 Analysis of Algorithms To determine how efficiently an algorithm solves a problem, we need to analyze the algorithm. We introduced efficiency analysis of algorithms when we compared the algorithms in the preceding section. However, we did those analyses rather informally. We will now discuss terminology used in analyzing algorithms and the standard methods for doing analyses. We will adhere to these standards in the remainder of the text. ### 1.3.1 Complexity Analysis When analyzing the efficiency of an algorithm in terms of time, we do not determine the actual number of CPU cycles because this depends on the particular computer on which the algorithm is run. Furthermore, we do not even want to count every instruction executed, because the number of instructions depends on the programming language used to implement the algorithm and the way the programmer writes the program. Rather, we want a measure that is independent of the computer, the programming language, the programmer, and all the complex details of the algorithm such as incrementing of loop indices, setting of pointers, and so forth. We learned that [Algorithm 1.5](LiB0009.html#38) is much more efficient than [Algorithm 1.1](LiB0008.html#27) by comparing the numbers of comparisons done by the two algorithms for various values of *n*, where *n* is the number of items in the array. This is a standard technique for analyzing algorithms. In general, the running time of an algorithm increases with the size of the input, and the total running time is roughly proportional to how many times some basic operation (such as a comparison instruction) is done. We therefore analyze the algorithm's efficiency by determining the number of times some basic .operation is done as a function of the size of the input. For many algorithms it is easy to find a reasonable measure of the size of the input, which we call the ***input size.*** For example, consider [Algorithms 1.1](LiB0008.html#27) (Sequential Search), [1.2](LiB0008.html#31) (Add Array Members), [1.3](LiB0008.html#32) (Exchange Sort), and [1.5](LiB0009.html#38) (Binary Search). In all these algorithms, *n*, the number of items in the array, is a simple measure of the size of the input. Therefore, we can call *n* the input size. In [Algorithm 1.4](LiB0008.html#34) (Matrix Multiplication), *n*, the number of rows and columns, is a simple measure of the size of the input. Therefore, we can again call *n* the input size. In some algorithms, it is more appropriate, to measure the size of the input using two numbers. For example, when the input to an algorithm is a graph, we often measure the size of the input in terms of both the number of vertices and the number of edges. Therefore, we say that the input size consists of both parameters. Sometimes we must be cautious about calling a parameter the input size. For example, in [Algorithms 1.6](LiB0009.html#45) (*n*th Fibonacci Term, Recursive) and [1.7](LiB0009.html#51) (*n*th Fibonacci Term, Iterative), you may think that *n* should be called the input size. However, *n* is the input; it is not the *size* of the input. For this algorithm, a reasonable measure of the size of the input is the number of symbols used to encode *.* If we use binary representation, the input size will be the number of bits it takes to encode *n*, which is \[l*g n*\] + 1. For example,  Therefore, the size of the input *n* = 13 is 4. We gained insight into the relative efficiency of the two algorithms by determining the number of terms each computes as a function of *n*, but still *n* does not measure the size of the input. These considerations will be important in [Chapter 9](LiB0074.html#880), where we will discuss the input size in more detail. Until then it will usually suffice to use a simple measure, such as the number of items in an array, as the input size. After determining the input size, we pick some instruction or group of instructions such that the total work done by the algorithm is roughly proportional to the number of times this instruction or group of instructions is done. We call this instruction or group of instructions the ***basic operation*** in the algorithm. For example, *x* is compared with an item *S* in each pass through the loops in [Algorithms 1.1](LiB0008.html#27) and [1.5](LiB0009.html#38). Therefore, the compare instruction is a good candidate for the basic operation in each of these algorithms. By determining how many times [Algorithms 1.1](LiB0008.html#27) and [1.5](LiB0009.html#38) do this basic operation for each value of *n*, we gained insight into the relative efficiencies of the two algorithms. In general, a ***time complexity analysis*** of an algorithm is the determination of how many times the basic operation is done for each value of the input size. Although we do not want to consider the details of how an algorithm is implemented, we will ordinarily assume that the basic operation is implemented as efficiently as possible. For example, we assume that [Algorithm 1.5](LiB0009.html#38) is implemented such that the comparison is done just once in each pass through the while loop. In this way, we analyze the most efficient implementation of the basic operation. There is no hard-and-fast rule for choosing the basic operation. It is largely a matter of judgment and experience. As already mentioned, we ordinarily do not include the instructions that make up the control structure. For example, in [Algorithm 1.1](LiB0008.html#27) we do not include the instructions that increment and compare the index in order to control the passes through the while loop. Sometimes it suffices simply to consider one pass through a loop as one execution of the basic operation. At the other extreme, for a very detailed analysis, one could consider the execution of each machine instruction as doing the basic operation once. As mentioned earlier, because we want our analyses to remain independent of the computer, we will never do that in this text. At times we may want to consider two different basic operations. For example, in an algorithm that sorts by comparing keys, .we often want to consider the comparison instruction and the assignment instruction each individually as the basic operation. By this we do not mean that these two instructions together compose the basic operation, but rather that we have two distinct basic operations, one being the comparison instruction and the other being the assignment instruction. We do this because ordinarily a sorting algorithm does not do the same number of comparisons as it does assignments. Therefore, we can gain more insight into the efficiency of the algorithm by determining how many times each is done. Recall that a time complexity analysis of an algorithm determines how many times the basic operation is done for each value of the input size. In some cases the number of times it is done depends not only on the input size, but also on the input's values. This is the case in [Algorithm 1.1](LiB0008.html#27) (Sequential Search). For example, if *x* is the first item in the array, the basic operation is done once, whereas if *x* is not in the array, it is done *n* times. In other cases, such as [Algorithm 1.2](LiB0008.html#31) (Add Array Members), the basic operation is always done the same number of times for every instance of size *n.*. When this is the case, ***T(n)*** is defined as the number of times the algorithm does the basic operation for an instance of size *n.* *T(n)* is called the ***every-case time complexity*** of the algorithm, and the determination of *T(n)* is called an ***every-case time complexity analysis.*** Examples of every-case time complexity analyses follow. ****Analysis of algorithm 1.2 Every-Case Time Complexity (Add Array Members)Other than control instructions, the only instruction in the loop is the one that adds an item in the array to *sum.* Therefore, we will call that instruction the basic operation. - Basic operation: the addition of an item in the array to *sum.* - Input size: *n*, the number of items in the array. Regardless of the values of the numbers in the array, there are *n* passes through the **for** loop. Therefore, the basic operation is always done *n* times and  **** ****Analysis of algorithm 1.3 Every−Case Time Complexity (Exchange Sort)As mentioned previously, in the case of an algorithm that sorts by comparing keys, we can consider the comparison instruction or the assignment instruction as the basic operation. We will analyze the number of comparisons here. - Basic operation: the comparison of *S\[j\]* with *S\[i\].* - In put size: *n*, the number of items to be sorted. We must determine how many passes there are through the for-*j* loop. For a given *n* there are always *n* − 1 passes through the for-*i* loop. In the first pass through the for-*i* loop, there are *n* − 1 passes through the for-*j* loop, in the second pass there are *n* − 2 passes through the for-*j* loop, in the third pass there are *n* - 3 passes through the for-*j* loop, . . . ., and in the last pass there is one pass through the for-*j* loop. Therefore, the total number of passes through the for-*j* loop is given by  The last equality is derived in [Example A.1](LiB0095.html#1293) in [Appendix A](LiB0093.html#1281). **** ****Analysis of Algorithm 1.4 Every-Case Time Complexity (Matrix Multiplication)The only instruction in the innermost for loop is the one that does a multiplication and an addition. It is not hard to see that the algorithm can be implemented in such a way that fewer additions are done than multiplications. Therefore, we will consider only the multiplication instruction to be the basic operation. - Basic operation: multiplication instruction in the innermost for loop. - In put size: *n*, the number of rows and columns. There are always *n* passes through the for-*i* loop, in each pass there are always *n* passes through the for-*j* loop, and in each pass through the for-*j* loop there are always *n* passes through the for-*k* loop. Because the basic operation is inside the for-*k* loop,  **** As discussed previously, the basic operation in [Algorithm 1.1](LiB0008.html#27) is not done the same number of times for all instances of size *n.* So this algorithm does not have an every-case time complexity. This is true for many algorithms. However, this does not mean that we cannot analyze such algorithms, because there are three other analysis techniques that can be tried. The first is to consider the maximum number of times the basic operation is done. For a given algorithm, **W**(*n)* is defined as the maximum number of times the algorithm will ever do its basic operation for an input size of *n.* So *W(n)* is called the **worstcase time complexity** of the algorithm, and the determination of *W*(*n*) is called a ***worst-case time complexity analysis.*** If *T*(*n*) exists, then clearly *W*(*n*) = *T*(*n*). The following is an analysis of *W*(*n*) in a case in which *T*(*n*) does not exist. ****Analysis of Algorithm 1.1 Worst−Case Time Complexity (Sequential Search)- Basic operation: the comparison of an item in the array with *x.* - Input size: *n*, the number of items in the array. The basic operation is done at most *n* times, which is the case if *x* is the last item in the array or if *x* is not in the array. Therefore,  **** Although the worst-case analysis informs us of the absolute maximum amount of time consumed, in some cases we may be more interested in knowing how the algorithm performs on the average. For a given algorithm, ***A(n***) is defined as the average (expected value) of the number of times the algorithm does the basic operation for an input size of *n.* (See [Section A.8.2](LiB0100.html#1349) in [Appendix A](LiB0093.html#1281) for a discussion of average.) *A(n*) is called the ***average-case time complexity*** of the algorithm, and the determination of *A*(*n*) is called an ***average-case time complexity analysis.*** As is the case for *W*(*n*), if *T*(*n*) exists, then *A*(*n*) = *T*(*n*). To compute A(n), we need to assign probabilities to all possible inputs of size *n.* It is important to assign probabilities based on all available information. For example, our next analysis will be an average-case analysis of [Algorithm 1.1](LiB0008.html#27). We will assume that if *x* is in the array, it is equally likely to be in any of the array slots. If we know only that *x* may be somewhere in the array, our information gives us no reason to prefer one array slot over another. Therefore, it is reasonable to assign equal probabilities to all array slots. This means that we are determining the average search time when we search for all items the same number of times. If we have information indicating that the inputs will not arrive according to this distribution, we should not use this distribution in our analysis. For example, if the array contains first names and we are searching for names that have been chosen at random from all people in the United States, an array slot containing the common name "John" will probably be searched more often than one containing the uncommon name "Felix" (see [Section A.8.1](LiB0100.html#1340) in [Appendix A](LiB0093.html#1281) for a discussion of randomness). We should not ignore this information and assume that all slots are equally likely. As the following analysis illustrates, it is usually harder to analyze the average case than it is to analyze the worst case. ****Analysis of Algorithm 1.1 Average-Case Time Complexity (Sequential Search)- Basic operation: the comparison of an item in the array with *x.* - Input size: *n*, the number of items in the array. We first analyze the case in which it is known that *x* is in *S*, where the items in *S* are all distinct, and where we have no reason to believe that *x* is more likely to be in one array slot than it is to be in another. Based on this information, for 1 ≤ *k* ≤ *n*, the probability that *x* is in the *k*th array slot is 1/*n.* If *x* is in the *k*th array slot, the number of times the basic operation is done to locate *x* (and, therefore, to exit the loop) is *k.* This means that the average time complexity is given by  The third step in this quadruple equality is derived in [Example A.1](LiB0095.html#1293) of [Appendix A](LiB0093.html#1281). As we would expect, on the average, about half the array is searched. Next we analyze the case in which *x* may not be in the array. To analyze this case we must assign some probability *p* to the event that *x* is in the array. If *x* is in the array, we will again assume that it is equally likely to be in any of the slots from 1 to *n.* The probability that *x* is in the *k*th slot is then *p/n*, and the probability that it is not in the array is 1 − *p.* Recall that there are *k* passes through the loop if *x* is found in the *k*th slot, and *n* passes through the loop if *x* is not in the array. The average time complexity is therefore given by  The last step in this triple equality is derived with algebraic manipulations. If *p* = 1, *A*(*n*) = (*n* + 1)/2, as before, whereas if *p* = 1/2, *A*(*n*) = 3*n*/4 + 1/4. This means that about 3/4 of the array is searched on the average. **** Before proceeding, we offer a word of caution about the average. Although an average is often referred to as a typical occurrence, one must be careful in interpreting the average in this manner. For example, a meteorologist may say that a typical January 25 in Chicago has a high of 22° F because 22° F has been the average high for that date over the past 80 years. The paper may run an article saying that the typical family in Evanston, Illinois earns $50,000 annually because that is the average income. An average can be called "typical" only if the actual cases do not deviate much from the average (that is, only if the standard deviation is small). This may be the case for the high temperature on January 25. However, Evanston is a community with families of diverse incomes. It is more typical for a family to make either $20,000 annually or $100,000 annually than to make $50,000. Recall in the previous analysis that *A*(*n*) is (*n* + 1)/2 when it is known that *x* is in the array. This is not the typical search time, because all search time between 1 and *n* are equally typical. Such considerations are important in algorithms that deal with response time. For example, consider a system that monitors a nuclear power plant. If even a single instance has a bad response time, the results could be catastrophic. It is therefore important to know whether the average response time is 3 seconds because all response times are around 3 seconds or because most are 1 second and some are 60 seconds. A final type of time complexity analysis is the determination of the smallest number of times the basic operation is done. For a given algorithm, ***B***(*n*) is defined as the minimum number of times the algorithm will ever do its basic operation for an input size of *n.* So *B*(*n*) is called the **best-case time complexity** of the algorithm, and the determination of *B(n*) is called a ***best-case time complexity analysis.*** As is the case for *W*(*n*) and *A*(*n*), if *T(n*) exists, then *B*(*n*) = *T*(*n*). Let's determine *B*(*n*) for [Algorithm 1.1](LiB0008.html#27). ****Analysis of Algorithm 1.1 Best-Case Time Complexity (sequential Search)- Basic operation: the comparison of an item in the array with *x.* - In put size: *n*, the number of items in the array. Because *n* ≥ 1, there must be at least one pass through the loop, If *x* = *S*\[1\], there will be one pass through the loop regardless of the size of n. Therefore,  **** For algorithms that do not have every-case time complexities, we do worst-case and average-case analyses much more often than best-case analyses. An average-case analysis is valuable because it tells us how much time the algorithm would take when used many times on many different inputs. This would be useful, for example, in the case of a sorting algorithm that was used repeatedly to sort all possible inputs. Often, a relatively slow sort can occasionally be tolerated if, on the average, the sorting time is good. In [Section 2.4](LiB0018.html#173) we will see an algorithm, named Quicksort, that does exactly this. It is one of the most popular sorting algorithms. As noted previously, an average-case analysis would not suffice in a system that monitored a nuclear power plant. In this case, a worst-case analysis would be more useful because it would give us an upper bound on the time taken by the algorithm. For both the applications just discussed, a best-case analysis would be of little value. We have discussed only the analysis of the time complexity of an algorithm. All the same considerations just discussed also pertain to analysis of ***memory complexity***, which is an analysis of how efficient the algorithm is in terms of memory. Although most of the analyses in this text are time complexity analyses, we will occasionally find it useful to do a memory complexity analysis. In general, a *complexity function* can be any function that maps the positive integers to the nonnegative reals. When not referring to the time complexity or memory complexity for some particular algorithm, we will usually use standard function notation, such as *f*(*n*) and *g(n*), to represent complexity functions. Example 1.6****The functions  are all examples of complexity functions because they all map the positive integers to the nonnegative reals. **** ### 1.3.2 Applying the Theory When applying the theory of algorithm analysis, one must sometimes be aware of the time it takes to execute the basic operation, the overhead instructions, and the control instructions on the actual computer on which the algorithm is implemented. By "overhead instructions" we mean instructions such as initialization instructions before a loop. The number of times these instructions execute does not increase with input size. By "control instructions" we mean instructions such as incrementing an index to control a loop. The number of times these instructions execute increases with input size. The basic operation, overhead instructions, and control instructions are all properties of an algorithm and the implementation of the algorithm. They are not properties of a problem. This means that they are usually different for two different algorithms for the: same problem. Suppose we have two algorithms for the same problem with the following every-case time complexities: *n* for the first algorithm and *n*2 for the second algorithm. The first algorithm appears more efficient. Suppose, however, a given computer takes 1,000 times as long to process the basic operation once in the first algorithm as it takes to process the basic operation once in the second algorithm. By "process" we mean that we are including the time it takes to execute the control instructions. Therefore, if *t* is the time required to process the basic operation once in the second algorithm, 1,000*t* is the time required to process the basic operation once in the first algorithm. For simplicity, let's assume that the time it takes to execute the overhead instructions is negligible in both algorithms. This means the times it takes the computer to process an instance of size *n* are *n* × 1,000*t* for the first algorithm and *n*2 × *t* for the second algorithm. We must solve the following inequality to determine when the first algorithm is more efficient:  Dividing both sides by *nt* yields  If the application never had an input size larger than 1,000, the second algorithm should be implemented. Before proceeding, we should point out that it is not always so easy to determine precisely when one algorithm is faster than another. Sometimes we must use approximation techniques to analyze the inequalities obtained by comparing two algorithms. Recall that we are assuming that the time it takes to process the overhead instructions is negligible. If this were not the case, these instructions would also have to be considered to determine when the first algorithm would be more efficient. ### 1.3.3 Analysis of Correctness In this text, "analysis of aft algorithm" means an efficiency analysis in terms of either time or memory. There are other types of analyses. For example, we can analyze the correctness of an algorithm by developing a proof that the algorithm actually does what it is supposed to do. Although we will often informally show that our algorithms are correct and will sometimes prove that they are, you should see Dijkstra (1976), Gries (1981), or Kingston (1990) for a comprehensive treatment of correctness.