edited by
3,718 views
0 votes
0 votes
In Quicksort let n/7​ th ​ smallest element is chosen using an O(n2​ ) algorithm as the
pivot. Calculate the worst case time complexity of the algorithm.
edited by

1 Answer

0 votes
0 votes
When n/7th element is chosen as pivot then array wiil be divided into two subparts having size n/7 and 6n/7. Time for doing this will be $O(n^2) $ as given, Recurrence relation can be written as:

$T(n)=T(\frac{n}{7})+T(\frac{6n}{7})+O(n^2)$ // can be solved using recursion tree also

For upper bound we can write as

$T(n)=2T(\frac{6n}{7})+O(n^2)$

Apply master's thorem,

T(n)=$O(nlog_{7/6}n)$

Related questions

3 votes
3 votes
1 answer
2
iarnav asked Jan 14, 2018
2,461 views
You have an array of n elements. Suppose you implement quick sort by always choosing the central element of the array as the pivot. Then the tightest lower bound for the...
3 votes
3 votes
3 answers
3
Sourajit25 asked Sep 3, 2017
1,615 views
"Quick sort has good cache performance" , Can anyone explain this statement.How is cache related to quick sort.I searched for this over the internet but could not find a ...
3 votes
3 votes
1 answer
4
SHALINI PORWAL asked Aug 10, 2017
1,357 views
When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?