QuickSelect average time complexity O(n) [HOW?]

Question

I was learning QuickSelect to find Kth Smallest Number. I understood the program. But I am stuck with how the average time complexity of QuickSelect is O(n).

I have tried the code in Java and it worked. But I am stuck with time complexity.

public class KthSmallestNumberUsingQuickSelect {

    int findKthNumber(int arr[], int left, int right, int k ) {
        if(k > 0 && k <= right - left + 1) {

            int pos = partition(arr,left,right);

            if(pos - left == k - 1)
                return arr[pos];

            if(pos - left > k - 1)
                return findKthNumber(arr, left, pos - 1, k);
            System.out.println(k - pos + left - 1);
            return findKthNumber(arr, pos + 1, right, k - pos + left - 1);
        }
        return Integer.MAX_VALUE;
    }

    int partition(int arr[], int left, int right) {
        int i = left ;
        int j;
        int x = arr[right];
        int temp = 0;

        for(j=left; j<right; j++ ) {
            if(arr[j] <= x) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
            }
        }
        temp = arr[i];
        arr[i] = x;
        arr[right] = temp;

        return i;
    }

    public static void main(String[] args) {
        KthSmallestNumberUsingQuickSelect kq = new KthSmallestNumberUsingQuickSelect();


        int arr[] =  {7,10,4,3,20,15};
        int k = 3;

        System.out.println(kq.findKthNumber(arr,0,arr.length-1, k));
    }
}

How is the average time complexity O(n)? Can anyone explain this to me in detail?

Answer 1

I think your question is not QuickSelect specific. You are asking what is the difference between the big O notation and the average Theta (Θ) notation.

The big O notation describes the biggest potential complexity that the algorithm will use.

On the other hand the Θ notation is the average complexity out all the possible combinations of the input for the problem.

There is also the omega (Ω) notation for the best case complexity.

The quick select algorithm follows similar complexity to quick sort and you are right the big O notation for both is O(n^2), but in the average case they are better.

If you need more specific explanation why the average case is linear read the answer in this post.