Page 504 - Discrete Mathematics and Its Applications

7.4 Expected Value and Variance 483

Finding the average-case computational complexity of an algorithm is usually much more
difficult than finding its worst-case computational complexity, and often involves the use of
sophisticated methods. However, there are some algorithms for which the analysis required
to find the average-case computational complexity is not difficult. For instance, in Example 8
we will illustrate how to find the average-case computational complexity of the linear search
algorithm under different assumptions concerning the probability that the element for which we
search is an element of the list.

EXAMPLE 8 Average-Case Complexity of the Linear Search Algorithm We are given a real number x
and a list of n distinct real numbers. The linear search algorithm, described in Section 3.1,
locates x by successively comparing it to each element in the list, terminating when x is located
or when all the elements have been examined and it has been determined that x is not in the
list. What is the average-case computational complexity of the linear search algorithm if the
probability that x is in the list is p and it is equally likely that x is any of the n elements in the
list? (There are n + 1 possible types of input: one type for each of the n numbers in the list and
a last type for numbers not in the list, which we treat as a single input.)

Solution: In Example 4 of Section 3.3 we showed that 2i + 1 comparisons are used if x equals
the ith element of the list and, in Example 2 of Section 3.3, we showed that 2n + 2 comparisons
are used if x is not in the list. The probability that x equals a i , the ith element in the list, is
p/n, and the probability that x is not in the list is q = 1 − p. It follows that the average-case
computational complexity of the linear search algorithm is

3p 5p (2n + 1)p
E = + + ··· + + (2n + 2)q
n n n
p
= (3 + 5 + ··· + (2n + 1)) + (2n + 2)q
n
p 2
= ((n + 1) − 1) + (2n + 2)q
n
= p(n + 2) + (2n + 2)q.

(The third equality follows from Example 2 of Section 5.1.) For instance, when x is guaranteed
to be in the list, we have p = 1 (so the probability that x = a i is 1/n for each i) and q = 0.
Then E = n + 2, as we showed in Example 4 in Section 3.3.
When p, the probability that x is in the list, is 1/2, it follows that q = 1 − p = 1/2,
so E = (n + 2)/2 + n + 1 = (3n + 4)/2. Similarly, if the probability that x is in the list
is 3/4, we have p = 3/4 and q = 1/4, so E = 3(n + 2)/4 + (n + 1)/2 = (5n + 8)/4.
Finally, when x is guaranteed not to be in the list, we have p = 0 and q = 1. It follows that
E = 2n + 2, which is not surprising because we have to search the entire list. ▲

Example 9 illustrates how the linearity of expectations can help us find the average-case
complexity of a sorting algorithm, the insertion sort.

EXAMPLE 9 Average-Case Complexity of the Insertion Sort What is the average number of comparisons
used by the insertion sort to sort n distinct elements?

Solution:We first suppose that X is the random variable equal to the number of comparisons used
by the insertion sort (described in Section 3.1) to sort a list a 1 ,a 2 ,...,a n of n distinct elements.
Then E(X) is the average number of comparisons used. (Recall that at step i for i = 2,...,n,
the insertion sort inserts the ith element in the original list into the correct position in the sorted
list of the first i − 1 elements of the original list.)