Question

1. Show that the select (selection by partition) algorithm in the lecture on order statistics has worst-case complexity O(n^2 ).

Answer 1

ANSWER:

GIVEN THAT:

THE ALGORITHM IN THE LECTURE ON ORDER STATISTICS:

Select function to find kth element is given here :
(l= left most index. r= right most index. pi= pivot index. list=> list of elements.)
function select(list, l, r, k)
         if l = r
             return list[l]
         pi := ...     // select Pivot index between left most element and right most element 
         pi := partition(list, l, r, pi) 
         if k = pi
             return list[k]
         else if k < pi
             r := pi - 1
             return select(list, l, r, k)
         else
             l := pi + 1 
             return select(list, l, r, k)

Here,

1. Partition algorithm ( from Quick sort) takes O(n) time.

2. Here Select procedure depends on pivot selection, if pivot is median or near to median then recursive call Select will consider either left most or right most partition of list of size n/2 . (considering n elements in list)

3. But if pivot is some index which is near to left most or right most index then recursive call Select will have at most n-1 elements.

3. So in worst case, i.e in worst selection of pivot, the recursive call will be for n-1 elements.

HENCE

4. RECURSIVE FUNCTION CAN BE WRITTEN AS :

5. BY SOLVING RECURSIVE RELATION :

  

Tín – 3) + (m - 2) + (m - 1)+n

..

  

T(1)+2+...+(n - 2) +(n - 1) + n

  

n* (n +1)

  

0(m2)

HENCE,

For worst case , Time complexity is $O(n^{2})$ .