314
Sets, Combinatorics, and Probability
PraCtiCe 48 From the expected value in Example 75, we “expect” to get 100 heads if we toss a fair coin
200 times. Find the actual probability of getting 100 heads out of 200 trials.
■
average Case analysis of algorithms
Previously, we have done primarily worst-case analysis of algorithms (Section 3.3).
Expected value may help give an average case analysis of an algorithm, i.e., tell
us the expected “average” amount of work performed by an algorithm. As in any
algorithm analysis, the first step is to identify a suitable “unit of work” based on
the nature of the algorithm. Then let the sample space S be the set of all possible
inputs to the algorithm. We’ll assume that S is finite; while there may be an infinite
number of distinct input values, we can group together those with the same work
unit characteristics. Let the random variable X assign to each member of S the
number of work units required to execute the algorithm on that input. And let p
be a probability distribution on S (here is where we make assumptions about what
constitutes “average” input). Then
E(X ) = ∙
n
i=1
X(x i )p(x i )
gives the expected number of work units.
example 76
Consider the sequential search algorithm (Section 3.3). The work unit is the number of comparisons of a target element x against the n elements in a list. Assume
that the target element is in the list and is equally likely to be any of the n elements
of the list (see Exercise 35 of Section 3.3). This assumption gives the table
x i
L 1
L 2
c
L n
X(x i )
1
2
c
n
p(x i )
1/n
1/n
c
1/n
Then
E(X ) = ∙
n
i=1
X(x i )p(x i )
= ∙
n
i=1
ia
1
n
b =
1
n ∙
n
i=1
i =
1
n
(1 + 2 + c + n) =
1
n
n(n + 1)
2
=
n + 1
2
The average number of comparisons to find a target in the list, with a uniform
probability distribution, is a little more than half the length of the list.