Medians and Order Statistics

9.1.1. First of all, make sure that for finding the maximum element out of 'n' elements will take 'n-1' comparisions. Now, when you're through this, let us suppose that you compared the elements by making a pair each time. For better understanding go through the below diagram:

Now, the second maximum element would've compared with the maximum somewhere between the heigth of the tree which will be log(n) as it'll always be a balanced tree. So, we can traverse the tree from the root(which is the maximum element) and compare the elements only in that path to find the maximum among them. As there'll be a maximum of log(n) elements along this path, so the maximum element can be found in log(n)-1 comparisions.

So, in total n+log(n)-2 comparisions will be needed to find the maximum and the second maximum element.

 

9.1.2. This is also very similar to above problem in which we need to compare elements by making pairs. Try Yourself!!!

9.2.1. This is very simple, for any 0-length array (p == q) will evaluates to true and the function will return from there.

9.2.3.

9.2.4. Following can be one of the worst-case performance of randomized selection:

                        (i.) 2, 9, 0, 7, 5, 4, 8, 6, 1

                        (ii.) 9, 0, 7, 5, 4, 8, 6, 1

                        (iii.) 0, 7, 5, 4, 8, 6, 1

                        (iv.) 0, 7, 5, 4, 8, 6

                        (v.) 0, 7, 5, 4, 8

                        (vi.) 0, 7, 5, 4

                        (vii.) 0, 7, 5

                        (viii.) 0, 7

                        (ix.) 0

 

9.3.3. For achieving worst case O(nlogn) complexity for quicksort we can replace the partition in the traditional algorithm for quicksort with

       SELECT procedure mentioned in the article.

9.3.5. Given the black box, after every partition we are sure that the given element either lies to left or to the right side of the partition.

       Thus we need to search only n/2 elements for 2nd iteration. Thus the time complexity can be found as:

    c*n + c*n/2 + c*n/4 + c*n/6 + ... = 2*c*n

       so, our selection algorithm will have O(n) complexity given the linear time black box.

9.3.7. First of all find the median of the 'n' elements, suppose that index is 'i (=n/2)'. Now the 'k' elements that are closest to the median are 

       those which are (i-k/2) and (i+k/2) distance from the median. So, just find the (i+k/2)th element and (i-k/2)th element. Thus, the 'k' 

       elements which are 'k' distance from the median are the elements from (i-k/2) to (i+k/2).  

9.3.9. In order to Þnd the optimal placement for Professor Olay’s pipeline, we need only and the median(s) of the y-coordinates of his oil wells.

       The optimal y-coordinate for Professor Olay’s east-west oil pipeline is as follows:

• If n is even, then on either the oil well whose y-coordinate is the lower median or the one whose y-coordinate is the upper median, or anywhere between them.

• If n is odd, then on the oil well whose y-coordinate is the median.

       The proof is quite simple and can be easily cracked. Try it yourself.

9.1. (a.) The best algorithm will have O(nlogn) complexity. Then finding the i largest element can be done in O(i).

          So, overall complexity will be O(nlogn + i).

     (b.) Building a max-priority queue is O(n) complexity. Then extracting largest 'i' elements can be done with O(ilogi) complexity.

          So, overall complexity will be O(n + ilogi).

  

     (c.) Use the SELECT algorithm of Section 9.3 to Þnd the i th largest number in (n) time. Partition around that number in (n) time. Sort the i largest numbers in

 (i lg i ) worst-case time (with merge sort or heapsort).

          So, overall running time will be: (n + i lg i ).