retagged by
2,513 views

2 Answers

0 votes
0 votes
Correct answer is O(n log (base 4/5) n) so according to ans it would be O(n logn)

Here T(n) = O(n) + T(n/5) + T(4n/5)

T(n) = Cn+T(n/5)+T(4n/5) here

we will make recurrence tree between which will be between n/5 and 4n/5

and you will get n/(4n/5)^k = 1

 k = log (base 4/5) n

so Cn* (log (base 4/5) n) = o(nlogn)

Related questions

4 votes
4 votes
2 answers
1
worst_engineer asked Oct 7, 2015
5,909 views
In quick sort , for sorting n elements , the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What will be the time complexity?it is $\Theta (...
4 votes
4 votes
3 answers
2
Swati verma asked Jun 21, 2017
7,584 views
Time complexity of quick sort when we take pivot from the middle element
0 votes
0 votes
1 answer
3
sh!va asked Jul 13, 2016
5,844 views
A desirable choice for the partitioning element in quick sort is(A) First element of the list(B) Last element of the list(C) Randomly chosen element of the list(D) Median...
0 votes
0 votes
1 answer
4