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:

First find $T_2(n)=\Theta(n^{\log_4 5})$ using the Master Theorem, then substitute it into $T_1(n)=4T_1(n/2)+T_2(n)$ and compare $n^{\log_4 5}$ with $n^2$ to apply Master Theorem Case 1 again.

Answer 1

The Correct Option is A

Step 1: Solve for \(T_2(n)\) using the Master Theorem.

\[T_2(n) = 5T_2\left(\frac{n}{4}\right) + \Theta(\log_2 n)\]

Here \(a=5\), \(b=4\), so \(n^{\log_b a} = n^{\log_4 5} \approx n^{1.16}\). Since \(f(n)=\Theta(\log_2 n)\) grows polynomially slower than \(n^{\log_4 5}\), i.e. \(f(n) = O(n^{\log_4 5 - \epsilon})\) for some \(\epsilon>0\), Master Theorem Case 1 applies:

\[T_2(n) = \Theta\left(n^{\log_4 5}\right)\]

Step 2: Substitute \(T_2(n)\) into the recurrence for \(T_1(n)\).

\[T_1(n) = 4T_1\left(\frac{n}{2}\right) + T_2(n) = 4T_1\left(\frac{n}{2}\right) + \Theta\left(n^{\log_4 5}\right)\]

Here \(a=4\), \(b=2\), so \(n^{\log_b a} = n^{\log_2 4} = n^{2}\).

Step 3: Compare \(f(n) = n^{\log_4 5}\) with \(n^2\). Since \(\log_4 5 \approx 1.16 < 2\), \(f(n) = O(n^{2-\epsilon})\) for some \(\epsilon>0\), so Master Theorem Case 1 applies again.

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

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