Randomized Quick Sort worst case Time Complexity

Question

Time complexity of Normal Quick Sort in worst case is O(n^2) when one of the following 2 cases occur:

Input is already sorted either in increasing or decreasing order
All elements in input array are same

In above two mentioned cases, PARTITION algorithms will divide array into two sub-parts, one with (n-1) elements and second with 0 elements

To avoid this bad case, we use another version of QuickSort i.e Randomized Quick-Sort, in which an random element is selected as pivot. The expected T.C of randomized quick-sort is theta(nlogn).

My question is, for what input/case, randmized Quick-Sort will result into worst time complexity of O(n^2)?

lf the randomised pivot selector happens to select e.g. the smallest element N times in a row, you will get the worst possible performance. The probability of this particular case is about 1/n! Of course there are more cases to consider. — n. 1.8e9-where's-my-share m.

Paul Hankin Paul Hankin · Accepted Answer · 2017-08-20T09:11:10

If the input contains elements that are all the same, the runtime of randomized quick-sort is O(n^2). That's assuming you're using the same PARTITION algorithm as in the deterministic version. The analysis is identical.

Here's an implementation of randomized quicksort which counts the number of compares performed:

import random

def quicksort(A, lo, hi):
    if lo >= hi:
        return 0
    p, compares = partition(A, lo, hi)
    compares += quicksort(A, lo, p - 1)
    compares += quicksort(A, p + 1, hi)
    return compares

def partition(A, lo, hi):
    r = random.randrange(lo, hi+1)
    A[r], A[hi] = A[hi], A[r]
    pivot = A[hi]
    i = lo - 1
    compares = 0
    for j in xrange(lo, hi):
        compares += 1
        if A[j] < pivot:
            i = i + 1
            A[i], A[j] = A[j], A[i]
    compares += 1
    if A[hi] < A[i + 1]:
        A[i + 1], A[hi] = A[hi], A[i + 1]
    return i + 1, compares


for x in xrange(10, 510, 40):
    compares = quicksort([1] * x, 0, x-1)
    print x, compares

The output clearly shows O(n^2) runtime:

Randomized Quick Sort worst case Time Complexity

1 Answers