Always show your work, no final answer is accepted without explanation.

Q$1$: Show that the second smallest of $n$ elements can be found with $n+|$~$lgn$~$|-2$ comparisons in the worst case. $($Hint: Also find the smallest element$)$

Q$2$: In the algorithm SELECT, the input elements are divided into groups of $5.$

a$)$ Will the algorithm work in linear time if they are divided into groups of $7?$

b$)$ Argue that SELECT does not run in linear time if groups of $3$ are used.

Q$3$: Show how quicksort can be run in $O(nlgn)$ time in worst case.

Q$4$: Suppose we use RANDOMIZED$-$SELECT to select the minimum element of the array $A=[3,2,9,0,7,5,4,8,6,1].$ Describe a sequence of partitions that results in a worst$-$case performance of RANDOMIZED$-$SELECT