Question

Discrete Math. What is the running time of the deterministic Select(A,n,i) for an arbitrary statistic i, 1 ≤ i ≤ n, and an array of n unordered keys? Give as tight an answer as you can.

Answer 1

Deterministic selection algorithm

Select(A,n,i) means to select the ith smallest number in the array A of n unordered keys,

one of the most naive algorithms that comes into mind is that we first sort the array and then find the ith element. The time complexity of this algorithm depends upon the sorting algorithm used, if we use bubble, insertion or selection sort, our complexity for sorting the array will be O(n^2). We can improve this by using some of the faster sorting algorithms that are merge sort, heap sort, etc, which bring down the complexity of sorting to O(nlogn), after sorting we will take the ith element and we will have the final answer. This algorithm has a worst case complexity of O(nlogn).

Another algorithm that comes into mind is that we can perform a binary search on the element we need to find. The meaning of this statement is that we define some upper and lower bound on the ith element, that is the lower bound will be the minimum element of our array and upper bound will be the maximum element of our array. Now with these H and L we find a mid which is (H+L)/2 and check whether this mid is the ith smallest element or not, for checking this we traverse the array and count the elements smaller than mid, if they are greater than or equal to i, then this mid can be the answer, but we still recursively call this binary search with H=mid, L=L and if we find that elements smaller than mid are less than i, we recursively call binary search with H=H, L=mid+1. Our binary search will converge at the ith smallest element.

Code(C++):

int smallerElements(int A[], int n, int mid){

    int ret=0;

    for(int i=0;i<n;i++){

    ret+=(mid<=A[i]);

    }

    return ret;

}

int binarySearch(int H, int L, int i, int A[], int n){

    int mid;

    int ans;    

    while(L<H){

    mid=(H+L)/2;

    if(smallerElements(A,n,mid)>=i){

    H=mid;

    ans=mid;

    }else{

    L=mid+1;

    }

    }

    return ans;

}

Let us analyse the time complexity of this algorithm, the smallerElements part takes O(n) time and the binary search will take O(log(Max(A[i])) time in worst case. So the worst case time complexity of this algorithm becomes O(n*log(max(A[i])) this better than the first case if the range of elements in A[i] is small.

Now we will see algorithms that have linear time complexity in the worst case.

For turning the expected time complexity to linear we use an algorithm that is similar to pivot selection in quick sort. We will call this optimised algorithm smartSelect. In smartSelect we will select a pivot which can be anything, the last element, the first element, or any random element, these selections may give a better time complexity on a specific test case but if we take an average over some of the random test cases, this selection has very little contribution in increasing or decreasing the time complexity. Now after selecting the pivot we will partition the array into two parts, one which will have all the elements smaller than pivot and other partition have all the elements larger than pivot. Now if we compare to quicksort algorithm, we will call the recursive function on both the parts, but in smartSelect we will call the recursive function only on that partition that will have the ith smallest element. If the partition containing the smaller element has the size greater than i, then we call the smartSelect on this partition and vice versa.  

ALGORITHM

select(A[0..n-1], i)

1) Divide the given array into n/5 groups of equal size( 5 here),

2) Sort the groups and find the median of all groups. Store the median of each group into another array(medians[]) of n/5 size,

3)Now, find the median of this medians[] using this function only ,recursively.

med1= select(medians[0..(⌈n/5⌉-1)], ⌈(n/5)/2⌉) // array median has n/5 elements

4) Partition A[] around med1 and obtain its index.

ind = partition(A, n, med1)   

// partition() divides the array about a particular element and put it at the correct index

// and return index.

5) If ind == i return med1

6) If ind > i return select(A[0..ind-1], i)

7) If ind < i return select(A[ind+1..n-1], i-ind-1)

Time Complexity:

The worst case time complexity of the above algorithm is O(n). Let us analyze all steps.

We calculate the median of an array of size 5, it will take O(5) time which is constant and since we have n/5 arrays of this type, the total time which finding the medians of all the arrays would be O(5*(n/5)) = O(n).

If we assume that we can find median of n element in T(n) time , then the next step will take T(n/5) time because the number of elements in median array is n/5.

Partitioning the array around a random element and getting position of pivot element in sorted array will take O(n) time.

Out of last 2 steps ( ind <i or ind >i) one will be executed. We need to find time complexity of these recursive steps. It will either be a maximum number of elements greater than med1 or maximum number of elements smaller than med1.

Number of elements are greater than med1 :-

At least half of the medians found in step 2 are greater than or equal to med1. Thus, at least half of the n/5 groups contribute 3 elements that are greater than med1, except for the one group that has fewer than 5 elements. Therefore, the number of elements greater than med1 is at least.

$3\left ( \left [ \frac{1}{2}\left [ \frac{n}{5} \right ] \right ] -2\right ) \geq \frac{3n}{10}-6$

Number of elements are less than than med1 :-

In a similar way we find at least 3n/10 – 6 will be less than med1. The function recurs for at most n – (3n/10 – 6) which is 7n/10 + 6 elements.

By solving the recurrence we get

   T(n) <= O(n) + T(n/5) + T(7n/10 +6)

So our deterministic selection algorithm takes O(n) time. The worst-case running time of is therefore linear