#Applied Course

Question

In a variant of quick sort, the n/10th smallest element is selected in every recursive call using a Θ(n) time algorithm, which is the worst-case time complexity for this sorting algorithm.

T(n)=T(n/10)+T(9n/10)+O(n)

This is what I tried according to this complexity is – o(nlogn)
my doubt is in this question they are saying pivot is getting calculated by o(n) in every recursive call … can someone clarify this line what will be the effect of this on an algorithm?

 

Answer 1

Given an array of n elements,

you will find pivot element first, which is n/10^th smallest number in array, it will take O(n) time as given in question itself.

 

Call partition algorithm which will divide array based on the pivot element and return position of pivot element, and we know that it will also take O(n) time.

 

Now our array of size n is divided into 2 parts, one part has (n/10)-1 elements less or equal to pivot and other part has (9n/10) elements greater than pivot.

 

Now again call recursively until the whole array is sorted.

 

So total time for n element array will be

T(n)=T(n/10)+T(9n/10)+n (to find pivot)+n (to perform partition)

T(n)=T(n/10)+T(9n/10)+2n

ignoring constants (so effect of that extra O(n) time is neglected while asymptotic analysis)

T(n)=T(n/10)+T(9n/10)+n

 

solving it using recursive tree method will give T(n)=O(nlogn).