The following recursive algorithm finds the k-th smallest element. It is assumed that the list

contains at least k elements. (Hint: This algorithm is similar to quicksort)

func select(list, left, right, k) if left = right 

 return list[left] pivotIndex <- ... // select a pivotIndex between left and right pivotIndex <- partition(list, left, right, pivotIndex) // The pivot is now in its final sorted position if k = pivotIndex 

 return list[k] else if k < pivotIndex 

 return select(list, left, pivotIndex - 1, k) else 

 return select(list, pivotIndex + 1, right, k) 

(a) What is the best case complexity for this algorithm? Describe the circumstances that would result in that performance. (b) Give a recurrence relation for the worst case performance of this algorithm. Find the asymptotic complexity of your recurrence relation.