Recursion tree method is best than the Substitution method for solving a recurrence relation because in recursion tree 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 but in substitution method we make a guess for the solution and then we use mathematical induction to prove the guess is correct or incorrect.
Asymptotic Analysis of Recurrence Relation
Recurrence Relation:
\[ T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{n}{2}\right) + \Theta(n^2) \]
Solution Using Recursion Tree Method
Step 1: Recursion Tree Structure
The recursion tree has:
- Root node cost: \(\Theta(n^2)\)
- Two child nodes: \(T\left(\frac{n}{4}\right)\) and \(T\left(\frac{n}{2}\right)\)
- This pattern continues until reaching small subproblems
Step 2: Cost at Each Level
Level 0 (Root):
\[ \text{Cost} = n^2 \]
Level 1:
\[ \text{Left child} = \left(\frac{n}{4}\right)^2 = \frac{n^2}{16} \]
\[ \text{Right child} = \left(\frac{n}{2}\right)^2 = \frac{n^2}{4} \]
\[ \text{Total cost} = \frac{n^2}{16} + \frac{n^2}{4} = \frac{5n^2}{16} \]
Level 2:
\[ \text{Left-left} = \left(\frac{n}{16}\right)^2 = \frac{n^2}{256} \]
\[ \text{Left-right} = \left(\frac{n}{8}\right)^2 = \frac{n^2}{64} \]
\[ \text{Right-left} = \left(\frac{n}{8}\right)^2 = \frac{n^2}{64} \]
\[ \text{Right-right} = \left(\frac{n}{4}\right)^2 = \frac{n^2}{16} \]
\[ \text{Total cost} = \frac{21n^2}{256} \]
General Pattern:
\[ \text{Cost at level } k = n^2 \left(\frac{5}{16}\right)^k \]
Step 3: Summing Over All Levels
The total cost is an infinite geometric series:
\[ T(n) = n^2 + \frac{5n^2}{16} + \frac{25n^2}{256} + \cdots \]
With first term \(a = n^2\) and common ratio \(r = \frac{5}{16}\)
Since \(|r| < 1\), the series converges to:
\[ T(n) = \frac{a}{1 - r} = \frac{n^2}{1 - \frac{5}{16}} = \frac{16n^2}{11} \]
Step 4: Asymptotic Upper Bound
The root cost (\(n^2\)) dominates the entire series:
\[ T(n) = O(n^2) \]
Final Answer
The asymptotic upper bound of the recurrence relation is:
\[ \boxed{O(n^2)} \]