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

An alternative way to see this is to grow a recursion tree instead of quoting the theorem directly.

First handle the inner recurrence \(T_2(n) = 5T_2(n/4) + \Theta(\log_2 n)\). The branching factor is \(5\) and the input shrinks by a factor of \(4\) at each level, so the number of leaves at depth \(d = \log_4 n\) is \(5^{\log_4 n} = n^{\log_4 5}\), and each leaf contributes \(\Theta(1)\) work while the internal nodes contribute only \(\Theta(\log_2 n)\) per level, a total dominated by the leaves. So \(T_2(n) = \Theta(n^{\log_4 5})\), where \(\log_4 5 \approx 1.16\).

Now plug this into \(T_1(n) = 4T_1(n/2) + T_2(n)\). This recurrence branches \(4\) ways and halves the input each time, giving a driving term of \(n^{\log_2 4} = n^2\) from the branching structure itself, compared against the extra \(n^{1.16}\) term added at each node. Since \(1.16\) is far smaller than \(2\), the branching term \(n^2\) dominates the total cost at every level of the tree.

Summing the geometric contribution across all levels therefore gives \(T_1(n) = \Theta(n^2)\), matching Option A: \(T_1(n) = \Theta(n^2)\).