Please Solve this Recurrence Relation

Question

Q.  In Quick sort ,for sorting n element ,the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case tome complexity of the Quick sort?

a) O(n)

b) O(nlogn)

c) O(n2)

d) O(n2logn)

Answer 1

 (n/4)th smallest element is selected as pivot using an O(n).

n/4th smallest element will divide the array into two parts, one part will have 1/4th elements at LHS of pivot element (pivot element can be considered a part of LHS), and second part will have 3/4th elements at RHS of pivot element. As pivot element goes to its correct position every time.
We'll get following recurrence relation:
T(n) = T(n/4) + T(3n/4) + n

Solve this recurrence relation and you will get T.C as $n*log_{4/3}^{n}$

Comments

How to solve this type of recurrence relation.Please Explain

---

Either use recursive tree method to solve entire recurrence relation, or for simplicity ignore the T(n/4) part and solve following recurrence relation:
T(n) = T(3n/4) + n

Recurrence tree for this recurrence relation will have $log_{4/3}^{n}$ levels and cost at each level is O(n).
if you add the costs from each level it will come to $O(n*log_{4/3}^{n})$

for further reference:

https://www.quora.com/How-do-I-find-the-time-complexity-in-T-n-T-n-4-+-T-3n-4-+-cn