CODEWITHSUNDEEP
algorithmsortingrecursioncomplexity-theory
Mary Star
Mary Star

Reputation: 375

How can I find the recursive relation?

How can I find the recursive relation,that describes the cost of the Quicksort,if we want to partition the subproblems with ratio 9:1?

The algorithm of the Quicksort that I am looking is the following:

Quicksort(A,p,r)
      if p<r then
         q<- partition(A,p,r)
         Quicksort(A,p,q-1)
         Quicksort(A,q+1,r)

Upvotes: 1

Views: 173

Answers (1)

user2566092
user2566092

Reputation: 4661

Quicksort uses a randomly chosen pivot, so it's going to be hard to guarantee something close to a 9:1 ratio unless you try multiple pivots and spend linear time on each one to find out what ratio the pivot gives. However, let's assume that you use deterministic linear time order statistics generalization of linear time median finding. Then, your recursion relation is 

T(n) = T(0.9*n) + T(0.1*n) + O(n)

which will still solve to O(n log n), but the hidden constant will be larger.

Upvotes: 2

Related Questions