Given a total of N number of data and you are applying Quick

Given a total of N number of data, and you are applying Quick Sort on these data to sort, if after each partitioning about 1/4th data falls on the left side and remaining 3/4 th of the data falls on the right side. What is the recurrence relation for the Run Time algorithm? Assume runtime for partitioning is N.

Solution

Okay so in a Quick sort lets discuss the Best and Worst Case:-

Best case:-

Best Case Analysis

Recurrence Relation: T(0) = T(1) = 0 (base case)

T(N) = 2T(N/2) + N

solving the Relation, we get

T(N) = N logN

which is O(NlogN)

Worst Case:-

Recurrence Relation:

T(N) = N + T(N-1)

where we need to compare the element till the 2nd last index of the array except the Pivot, that is till the (N-1)th element.

So solving the relation we get

T(N) = N + T(N-1)

T(N-1) = (N-1) + T(N-2)

T(N-2) = (N-2) + T(N-3)

...

T(3) = 3 + T(2)

T(2) = 2 + T(1)

T(1) = 0

Hence, T(N) = N + (N-1) + (N-2) ... + 3 + 2 N²/2

which is O(N²) .

So, Now coming back to the Question.

Now in this Question as the left side is 1/4 of the Array and the Right side is 3/4 of the array,

So the Recurrence Relation of the Quicksort will be:-

T(N)=T(N/4)+T(3N/4)

Thank You for using Chegg...