# Recursion Tree for the recurrence \( T(n) = 3T(|n/4|) + n^2 \) ## Assumption - The recurrence is valid for \( n > 1 \). - We interpret \( |n/4| \) as \( n/4 \) assuming \( n \geq 1 \). --- ## Step 1: Breakdown of the recurrence - **Root level (Level ):** \[ T(n) \] Cost: \( n^2 \) - **Next level (Level 1):** \[ 3 \times T(n/4) \] Cost per subproblem: \( (n/4)^2 = n^2/16 \) - **Level 2:** Each subproblem splits into 3 subproblems: \[ 3^2 \times T(n/4^2) \] Cost per subproblem: \( (n/16)^2 = n^2/256 \) - And so on... --- ## Step 2: Constructing the recursion tree ### Level : - **Number of nodes:** 1 - **Cost at this level:** \( n^2 \) ### Level 1: - **Number of nodes:** 3 - **Cost per node:** \( (n/4)^2 = n^2/16 \) - **Total cost at this level:** \( 3 \times n^2/16 = 3n^2/16 \) ### Level 2: - **Number of nodes:** \( 3^2 = 9 \) - **Cost per node:** \( (n/4^2)^2 = n^2/4^4 = n^2/256 \) - **Total cost:** \( 9 \times n^2/256 = 9n^2/256 \) ### General Level \( i \): - **Number of nodes:** \( 3^i \) - **Size of each subproblem:** \( n/4^i \) - **Cost per node:** \( (n/4^i)^2 = n^2/16^i \) - **Total cost at level \( i \):** \[ 3^i \times \frac{n^2}{16^i} = n^2 \times \frac{3^i}{16^i} \] --- ## Step 3: Summation of costs across levels Total cost \( T(n) \) is approximately the sum over all levels: \[ T(n) \approx \sum_{i=}^{\log_4 n} n^2 \times \left( \frac{3}{16} \right)^i \] - The number of levels is \( \log_4 n \), since at each level, the problem size reduces by factor 4. --- ## Step 4: Recognizing the geometric series - The sum: \[ T(n) \approx n^2 \sum_{i=}^{\log_4 n} \left( \frac{3}{16} \right)^i \] - Since \( \frac{3}{16} < 1 \), this is a geometric series with ratio \( r = \frac{3}{16} \). - The sum of a finite geometric series: \[ \sum_{i=}^{k} r^i = \frac{1 - r^{k+1}}{1 - r} \] - As \( n \to \infty \), the sum converges to: \[ \frac{1}{1 - \frac{3}{16}} = \frac{1}{\frac{13}{16}} = \frac{16}{13} \] - The dominant term is: \[ T(n) = \Theta(n^2) \] --- ## **Summary:** - The recursion tree shows decreasing costs per level, forming a geometric series. - The total work is dominated by \( \Theta(n^2) \). --- ## **Visual Sketch (simplified):** ```plaintext Level : T(n) Cost: n^2 Level 1: 3 T(n/4) Cost per node: n^2/16 Total: 3 * n^2/16 Level 2: 9 T(n/16) Cost per node: n^2/256 Total: 9 * n^2/256 ... Total: T(n) ≈ n^2 * sum_{i=}^log_4 n (3/16)^i ≈ Θ(n^2) ``` --- **Note:** This analysis assumes the recurrence is valid for large \( n \) and ignores base cases.