Can you solve this by Master Method ?

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

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

The Gateway to Computer Science Excellence

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

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

+2 votes

0

Can you solve this by Master Method ?

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

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.6k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,833 questions

57,697 answers

199,350 comments

107,405 users