### Exercise

#### 1.14

Follow through the steps given for quicksort to solve the recurrence:

#### 1.15

Show that the average number of exchanges used during the first partitioning stage (before the pointers cross) is $(N-2)/6$.

#### 1.17

If we change the first line in the quicksort implementation given in the lecture to call insertion sort when the subfile size is not greater than $M$ then the total number of comparisons to sort $N$ elements is described by the recurrence

Solve this recurrence.

### Problem

#### 2

Which of the following is a drawback to analyzing algorithms by proving O- upper bounds on the worst case?

• Generally cannot be used to predict performance.
• Likely to be too much detail in the analysis.
• Generally cannot be used to compare algorithms.
• Input model may be unrealistic.

Generally cannot be used to predict performance.

Generally cannot be used to compare algorithms.