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)\) first, since \(T_1(n)\) depends on it. The recurrence \(T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)\) has the Master Theorem form \(T(n) = aT(n/b) + f(n)\) with \(a = 5\), \(b = 4\), and \(f(n) = \Theta(\log_2 n)\).

Step 2: Compute the critical exponent for \(T_2\). \(n^{\log_b a} = n^{\log_4 5}\). Since \(4^1 = 4\) and \(4^{1.16} \approx 5\), \(\log_4 5 \approx 1.16\), a bit more than 1.

Step 3: Compare \(f(n) = \log_2 n\) against \(n^{\log_4 5}\). A logarithm grows strictly slower than any positive power of \(n\), so \(\log_2 n = O(n^{\log_4 5 - \varepsilon})\) for a suitable small \(\varepsilon > 0\). Master Theorem Case 1 applies, giving \(T_2(n) = \Theta(n^{\log_4 5})\).

Step 4: Substitute this into the recurrence for \(T_1\). \(T_1(n) = 4T_1(n/2) + T_2(n) = 4T_1(n/2) + \Theta(n^{\log_4 5})\). This is again Master Theorem form with \(a = 4\), \(b = 2\), and \(f(n) = \Theta(n^{\log_4 5}) \approx \Theta(n^{1.16})\).

Step 5: Compute the critical exponent for \(T_1\). \(n^{\log_b a} = n^{\log_2 4} = n^2\).

Step 6: Compare \(f(n) \approx n^{1.16}\) against \(n^2\). Since \(1.16 < 2\), \(f(n)\) is polynomially smaller than \(n^{\log_b a} = n^2\). This is again Master Theorem Case 1, so the recursive term dominates and \(T_1(n) = \Theta(n^{\log_b a}) = \Theta(n^2)\).

Step 7: Why the other options are wrong. Options (B) and (D) include an extra logarithmic factor, that factor only appears in Master Theorem Case 2, which needs \(f(n) = \Theta(n^{\log_b a})\) exactly, but here the exponents \(1.16\) and \(2\) are not equal, so no log factor should appear. Option (C), \(\Theta(n^{\log_4 5})\), would be correct only if the extra term \(T_2(n)\) dominated the recursive part of \(T_1\) (Case 3), but \(n^{\log_4 5}\) grows slower than \(n^2\), not faster, so the recursive term \(4T_1(n/2)\) dominates instead.

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