Question

Consider the following recurrence relations. For all \(n > 1\),
\[ T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n) \]
\[ T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n) \]
Assume that for all \(n \leq 1\), \(T_1(n) = 1\) and \(T_2(n) = 1\).
Which one of the following options is correct?

• A. \(T_1(n) = \Theta(n^2)\)
• B. \(T_1(n) = \Theta(n^2 \log_2 n)\)
• C. \(T_1(n) = \Theta(n^{\log_4 5})\)
• D. \(T_1(n) = \Theta(n^{\log_4 5} \log_2 n)\)

Hint:

Solve \(T_2(n)\) with the Master Theorem to get \(\Theta(n^{\log_4 5})\), then substitute into \(T_1(n)\) and apply the Master Theorem again; since \(\log_4 5 < 2 = \log_2 4\), Case 1 gives \(T_1(n) = \Theta(n^2)\).

Answer 1

The Correct Option is A

Step 1: Solve $T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)$ by unrolling it as a recursion tree instead of quoting the Master Theorem directly. At depth $k$, there are $5^k$ nodes, each of size $n/4^k$, and the tree bottoms out at depth $k = \log_4 n$.

Step 2: The total number of leaves is $5^{\log_4 n} = n^{\log_4 5}$, and since each leaf contributes $\Theta(1)$ work and $\log_4 5 \approx 1.16 > 1$, the leaves dominate the total, summing the geometric series of per-level costs gives $\Theta(n^{\log_4 5})$, matching the Master Theorem Case 1 result for $T_2(n)$.

Step 3: Now unroll $T_1(n) = 4T_1(n/2) + T_2(n)$ the same way. At depth $k$ there are $4^k$ nodes of size $n/2^k$, bottoming out at depth $k = \log_2 n$, giving $4^{\log_2 n} = n^2$ leaves, each contributing $\Theta(1)$, so the leaves alone already cost $\Theta(n^2)$.

Step 4: The non-leaf cost injected at depth $k$ is $4^k \cdot T_2(n/2^k) = \Theta\big(n^{\log_4 5} \cdot (4/2^{\log_4 5})^k\big)$. Since $\log_4 5 \approx 1.16 < 2$, the ratio $4/2^{\log_4 5} \approx 1.79 > 1$, so this per-level cost grows with $k$ and is maximized at the deepest level $k = \log_2 n$, where it becomes exactly the $\Theta(n^2)$ leaf cost from Step 3 up to constants.

Step 5: Summing a geometric series dominated by its last (largest) term still gives $\Theta(n^2)$ overall, confirming without directly invoking the Master Theorem's case statement that $T_1(n) = \Theta(n^2)$, since neither the extra $T_2(n)$ term nor the higher levels of the tree change the order of growth set by the $n^2$ leaves.

\[ \boxed{T_1(n) = \Theta(n^2)} \]