. (2 points) Consider the selection problem: given an array of nnumbers (a1, a2, . . . , an) and an integer 1 ? k ? n, find thek-th smallest number in this array. A simple algorithm is to firstsort the array in O(n log n) time and then output the k-th element.In this exercise, we will try to derive an O(n) algorithm for thisproblem. Without loss of generality, we assume (a1, a2, . . . , an)are distinct and n is a power of 2. To make things easier, you aregiven access to an algorithm A which can find the median in lineartime. More specifically, for any even number t > 0, you can callalgorithm A on an array of t distinct numbers (b1, b2, . . . , bt).Algorithm A will run in time O(t) and output a number x such that|{i : bi ? x}| = t/2.
(a) Design a divide-and-conquer algorithm for the selectionproblem. Your algorithm should run in O(n) time.
(b) Prove the correctness of your algorithm and analyze itsrunning time
