algorithm - Randomized Quick Sort worst case Time Complexity -

time complexity of normal quick sort in worst case o(n^2) when 1 of following 2 cases occur:

1. input sorted either in increasing or decreasing order
2. all elements in input array same

in above 2 mentioned cases, partition algorithms divide array 2 sub-parts, 1 (n-1) elements , second 0 elements

to avoid bad case, use version of quicksort i.e randomized quick-sort, in random element selected pivot. expected t.c of randomized quick-sort theta(nlogn).

my question is, input/case, randmized quick-sort result worst time complexity of o(n^2)?

if input contains elements same, runtime of randomized quick-sort o(n^2). that's assuming you're using same partition algorithm in deterministic version. analysis identical.

here's implementation of randomized quicksort counts 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]     = lo - 1     compares = 0     j in xrange(lo, hi):         compares += 1         if a[j] < pivot:             = + 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 + 1, compares   x in xrange(10, 510, 40):     compares = quicksort([1] * x, 0, x-1)     print x, compares 

the output shows o(n^2) runtime:

10 54 50 1274 90 4094 130 8514 170 14534 210 22154 250 31374 290 42194 330 54614 370 68634 410 84254 450 101474 490 120294