Analysis of Algorithms : An Active Learning Approach

56 SEARCHING AND SELECTION ALGORITHMS

should be incremented just before the key comparison in your sequential

search routine. Your main program should then call sequential search for

each number between 1 and N. After doing this, the total count of compar-

isons divided by N will be the average number of comparisons done by

sequential search.

2. Repeat Step 1 for binary search, using an ordered list.


3. Write a report that compares your output from parts 1 and 2 with the results
   you would predict based on the analysis in this chapter.