216
Recursion, Recurrence Relations, and Analysis of Algorithms
pivot element, then walk through the original list to create two new sublists, L 1 and L 2 . L 1 consists of all elements
that are less than the pivot element and L 2 consists of all elements that are greater than the pivot element. Put the
pivot element between L 1 and L 2 . Sort each of L1 and L2 using QuickSort (this is the recursive part). Eventually
all lists will consist of 1 element sublists separated by previous pivot elements, and at this point the entire original
list is in sorted order. This is a little confusing, so here is an example, where pivot elements are shown in brackets:
Original list: 6, 2, 1, 7, 9, 4, 8
After 1st pass: 2, 1, 4, [6], 7, 9, 8
After 2nd pass: 1, [2], 4, [6], [7], 9, 8
After 3rd pass: 1, [2], 4, [6], [7], 8, [9]
Sorted
25. Illustrate QuickSort as above using the list 9, 8, 3, 13.
26. Illustrate QuickSort as above using the list 8, 4, 10, 5, 9, 6, 14, 3, 1, 12, 11.
27. How many comparisons between list elements are required for pass 1 of QuickSort in the example list?
28. How many comparisons between list elements are required for pass 1 of QuickSort on an n-element list?
29. Suppose that for each pass, each pivot element splits its sublist into two equal-length lists, each approximately half the size of the sublist (which is actually very difficult to achieve). Write a recurrence relation
for the number of comparisons between list elements in this case.
30. Solve the recurrence relation of Exercise 29.
31. Suppose that for each pass, each pivot element splits its sublist (which has k elements) into one empty list
and one list of size k − 1. Write a recurrence relation for the number of comparisons between list elements
in this case.
32. Solve the recurrence relation of Exercise 31.
33. Unlike the situation described in Exercise 29 where each pivot element splits the sublist in half for the next
pass, the situation described in Exercise 31 can easily occur. Describe a characteristic of the original list
that would cause this to happen.
34. Exercise 29 describes the best case of QuickSort and Exercise 31 describes the worst case of QuickSort
with respect to comparisons between list elements.
a. To which sorting algorithm (SelectionSort, BubbleSort, MergeSort) is the best case of QuickSort
comparable in the number of comparisons required?
b. To which sorting algorithm (SelectionSort, BubbleSort, MergeSort) is the worst case of QuickSort
comparable in the number of comparisons required?
Exercises 35 and 36 refer to algorithm SequentialSearch. It is not hard to do an average case analysis of the
sequential search algorithm under certain assumptions. Given an n-element list and a target value x for which
we are searching, the basic operation is a comparison of list elements to x, hence an analysis should count how
many times such an operation is performed “on the average.” The definition of “average” is shaped by our
assumptions.
35. Assume that x is in the list and is equally to be found at any of the n positions in the list. Fill in the rest of
the table giving the number of comparisons for each case.
position at Which x occurs number of comparisons
1
1
2
3
(
n
Recursion, Recurrence Relations, and Analysis of Algorithms
pivot element, then walk through the original list to create two new sublists, L 1 and L 2 . L 1 consists of all elements
that are less than the pivot element and L 2 consists of all elements that are greater than the pivot element. Put the
pivot element between L 1 and L 2 . Sort each of L1 and L2 using QuickSort (this is the recursive part). Eventually
all lists will consist of 1 element sublists separated by previous pivot elements, and at this point the entire original
list is in sorted order. This is a little confusing, so here is an example, where pivot elements are shown in brackets:
Original list: 6, 2, 1, 7, 9, 4, 8
After 1st pass: 2, 1, 4, [6], 7, 9, 8
After 2nd pass: 1, [2], 4, [6], [7], 9, 8
After 3rd pass: 1, [2], 4, [6], [7], 8, [9]
Sorted
25. Illustrate QuickSort as above using the list 9, 8, 3, 13.
26. Illustrate QuickSort as above using the list 8, 4, 10, 5, 9, 6, 14, 3, 1, 12, 11.
27. How many comparisons between list elements are required for pass 1 of QuickSort in the example list?
28. How many comparisons between list elements are required for pass 1 of QuickSort on an n-element list?
29. Suppose that for each pass, each pivot element splits its sublist into two equal-length lists, each approximately half the size of the sublist (which is actually very difficult to achieve). Write a recurrence relation
for the number of comparisons between list elements in this case.
30. Solve the recurrence relation of Exercise 29.
31. Suppose that for each pass, each pivot element splits its sublist (which has k elements) into one empty list
and one list of size k − 1. Write a recurrence relation for the number of comparisons between list elements
in this case.
32. Solve the recurrence relation of Exercise 31.
33. Unlike the situation described in Exercise 29 where each pivot element splits the sublist in half for the next
pass, the situation described in Exercise 31 can easily occur. Describe a characteristic of the original list
that would cause this to happen.
34. Exercise 29 describes the best case of QuickSort and Exercise 31 describes the worst case of QuickSort
with respect to comparisons between list elements.
a. To which sorting algorithm (SelectionSort, BubbleSort, MergeSort) is the best case of QuickSort
comparable in the number of comparisons required?
b. To which sorting algorithm (SelectionSort, BubbleSort, MergeSort) is the worst case of QuickSort
comparable in the number of comparisons required?
Exercises 35 and 36 refer to algorithm SequentialSearch. It is not hard to do an average case analysis of the
sequential search algorithm under certain assumptions. Given an n-element list and a target value x for which
we are searching, the basic operation is a comparison of list elements to x, hence an analysis should count how
many times such an operation is performed “on the average.” The definition of “average” is shaped by our
assumptions.
35. Assume that x is in the list and is equally to be found at any of the n positions in the list. Fill in the rest of
the table giving the number of comparisons for each case.
position at Which x occurs number of comparisons
1
1
2
3
(
n