The Gateway to Computer Science Excellence
+4 votes
899 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 ?
in Algorithms by Active (3.8k points) | 899 views

2 Answers

+10 votes
Best answer
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.1k points)
edited by
+2 votes
T(n)=T(n/4)+T(3n/4)+O(n)

Solving this using recurrence tree we get

T(n)=O(nlogn)
by Boss (31.2k 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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,654 questions
56,169 answers
193,881 comments
94,306 users