944 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 (n^{2})$ , right ?
| 944 views

It would be $\Theta \left(n\log{n} \right)$.

At each level, the array of size n is getting divided in to 2 sub arrays of size (n/4) and (3n/4) along with an extra work for choosing pivot which requires $O \left( n \right)$ time.

So recurrence will be of the form: $T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + O\left(n\right)$

This can be solved using recursion tree.

Lower bound for this recurrence will be $\Omega \left(n\log_{4}n \right)$, & upper bound will be $O \left(n\log_{\frac{4}{3}}n \right)$,

which gives $T(n) = \Theta \left(n\log{n} \right)$.
by Boss (14.3k points)
edited
T(n)=T(n/4)+T(3n/4)+O(n)

Solving this using recurrence tree we get

T(n)=O(nlogn)
by Boss (31.5k points)
0
Can you solve this by Master Method ?

Can you please show how are you evaluating it using recursion tree as well.
+2

Recurrence Tree Method: In this method, we draw a recurrence tree and calculate the time taken by every level of tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from the given recurrence and keep drawing till we find a pattern among levels. The pattern is typically a arithmetic or geometric series.

For example consider the recurrence relation which is given
T(n) = T(n/4) + T(3n/4) + cn

cn
/      \
T(n/4)     T(3n/4)

If we further break down the expression T(n/4) and T(3n/4),
we get following recursion tree.

cn
/           \
c(n)/4     c(3n)/4
/      \          /     \
T(n/16)     T(3n/16)  T(3n/16)    T(9n/16)

To know the value of T(n), we need to calculate sum of tree
nodes level by level.
@arjun sir please help me in writing correct recursion tree. I am getting confuse.