Question: In the Search for Value algorithm, the comparisons are made in Step 5. Under the assumption that the target is as likely to be in
In the Search for Value algorithm, the comparisons are made in Step 5. Under the assumption that the target is as likely to be in any one position in the list as in any other position, the best way to measure the number of comparisons is to average the number of comparisons required for the various positions of the target. Compute the average number of times that Step 5 must be executed for the eight-element list by averaging the numbers in the first eight rows of the Step 5 column of the table in Exercise 2.4. If the list only had seven elements, we would average the first seven of the numbers in this column. Try computing this average for a few values for the list size. Give a formula for the average number of comparisons if there are n elements in the list.
| target | step 1 | step 2 | step 3 | step 4 | step 5 | step 6 | step 7 | step 8 | step 9 | step 10 | step 11 |
| element 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ||||
| element 2 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 1 | |||
| element 3 | 1 | 1 | 1 | 3 | 3 | 1 | 1 | 2 | |||
| element 4 | 1 | 1 | 1 | 4 | 4 | 1 | 1 | 3 | |||
| element 5 | 1 | 1 | 1 | 5 | 5 | 1 | 1 | 4 | |||
| element 6 | 1 | 1 | 1 | 6 | 6 | 1 | 1 | 5 | |||
| element 7 | 1 | 1 | 1 | 7 | 7 | 1 | 1 | 6 | |||
| element 8 | 1 | 1 | 1 | 8 | 8 | 1 | 1 | 7 |
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help