Analysis of Algorithms : An Active Learning Approach

28 ANALYSIS BASICS

the leaves. At each level, two elements are paired and the larger of the two gets

copied into the parent node. This process continues until the root node is

reached. Figure 1.3 shows a complete tournament tree for a given set of data.

In Exercise 5 of Section 1.1.3, it was mentioned that we would develop an

algorithm to find the second largest element in a list using about N compari-

sons. The tournament method helps us do this. Every comparison produces

one “winner” and one “loser.” The losers are eliminated and only the winners

move up in the tree. Each element, except for the largest, must “lose” one

comparison. Therefore, building the tournament tree will take N
 1 com-

parisons.

The second largest element could only have lost to the largest element. We

go down the tree and get the set of elements that lost to the largest one. We

know that there can be at most lgN of these elements because of our tree

formulas in Section 1.3.2. There will be lgN comparisons to find these ele-

ments in the tree and lgN
 1 comparisons to find the largest in this collec-

tion. The entire process takes N + 2 lgN
 2 comparisons, which is O(N).

The tournament method could also be used to sort a list of values. In

Chapter 3, we will see a method called heapsort that is based on the tourna-

ment method.

■ 1.5.2 Lower Bounds

An algorithm is optimal when there is no algorithm that will work more

quickly. How do we know when have we found an algorithm that is optimal

or when is an algorithm not optimal, but good enough? To answer these ques-

8

6 8

6

46

3

32

8

87

5

15

■FIGURE 1.3

Tournament tree

for a set of eight

values