Question

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 ?

Comments

Hey Everyone

My doubt is that question should be more clear ..

because selection of pivot element can be done anyway

the first one or last one or the random pivot one,anything may be selected as pivot right?

so selecting a pivot element using some algorithm takes o(n) time as given in the question

but selection of pivot won't split the array into two parts right ?

the array is split after once the pivot gets settled at some position using partition algorithm

So as per that concept selecting pivot for the first time takes O(n) + the worst case of quick sort takes O(n²)

so total would be O(n²) only…

If the option b should be correct

the question should be like

some algorithm partitions the array with atleast n/4 elements in a partition

if asked like that answer would be option b

am i wrong now??

Answer 1

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)$.

Comments

A more clear picture:

T(n) = O(n) to find (n/4)th smallest + O(n) for partition +  T(n/4) + T(3n/4)

T(n) = 2O(n) + T(n/4) + T(3n/4)

Answer 2

T(n)=T(n/4)+T(3n/4)+O(n)

Solving this using recurrence tree we get

T(n)=O(nlogn)

Comments

Can you solve this by Master Method ?

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

---

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.