[6 marks]

Problem 1 When doing the average-case analysis of Quick-Select, we consid- ered a good  and a bad  case.  We said that a good case happened when, if i is the index of the pivot in the partitioned array,    ≤ i ≤  .  Suppose instead that a good case happens when  ≤ i ≤  . With this assumption, show that Quick-Select still runs in O(n) time in the average case.

Hint:  Start by finding the probabilities of a good or bad case happening, and use these to provide an upper bound for T(n).

Solution: Since good cases correspond to  of the possible ranks and bad cases correspond to the remaining  of the possible ranks, the probability of a good case is  and the probability of a bad case is  . In a good case, the size of the recursive call is at most   and in a bad case, the size of the recursive call is at most n. Now let T(n) be the average case running time of quickselect on an input of size n.  Suppose that partitioning takes at most cn time and that the base case takes d time, where c,d ∈ O(1). Then we know that

T(n) < cn + T   + T(n)

⇒3T(n) < 3cn + T   + 2T(n)

⇒T(n) < 3cn + T  

⇒T(n) < 3cn + 3 · 2cn + 3 · cn + ··· + d

⇒T(n) < 3cn ·   i + d ∈ Θ(n)

since the series converges to a constant.  Thus, the running time is in O(n) in the average case, completing the proof.

[5 + 5 = 10 marks]

Problem 2 Consider a variant of the Median-of-medians algorithm where, in- stead of partitioning the input into n/5 blocks of size 5, we partition the input into n/3 blocks of size 3.

(a) Follow the same steps as in the slides to derive a recursive formula T(n) for the time complexity of this algorithm.

Solution:  Let x be the selected median-of-medians.   Then at least half the blocks have medians at most x.   In these blocks,  2 elements are at most x. Thus, in total, there are  ·  · 2 =  elements that are at most x.  Similarly, there are  elements that are at least x. So, the size of the recursive call can be at most  . Let T(1) = d be the base case and suppose that partitioning takes at most cn time. Then, in the recursive case, we spend T   time finding the median-of-medians, cn time partitioning, and T    time on a recursive call. So,

T(n) ≤ T     + cn + T  

(b) Try to solve the recurrence by guessing that T(n) ∈ O(n).  Follow the same steps as in the slides and indicate whether we can state that T(n) ∈ O(n).

Solution: We would like to show that T(n) ∈ O(n) using strong induction. In particular, we should find an M > 0 so that T(n) ≤ Mn for all n ≥ 1. For the base case, we need only ensure that M ≥ d.  Now let n > 1 and suppose that T(k) ≤ Mk for all k ∈ {0, ··· ,n}. Then

T(n) ≤ T     + T   + cn

n             2n

3             3

= (M + c)n

We cannot find an M > 0 so that Mn ≤ (M + c)n, so we cannot follow the same steps to show that T(n) ∈ O(n).