Consider the following recurrence relations:
For all $n>1$ ,

$$T_1\left(n\right)=4T_1\left(\frac{n}{2}\right)+T_2\left(n\right)$$ $$T_2\left(n\right)=5T_2\left(\frac{n}{4}\right)+\Theta \left({\log }_{2}n\right)$$ Assume that for all $n\le 1$ , $T_1\left(n\right)=1$ and $T_2\left(n\right)=1$ .

Which one of the following options is correct?

The correct option is: T₁(n) = Θ(n²)

To find the asymptotic tight bound for $T_1\left(n\right)$, we need to solve the system of recurrence relations step-by-step.

Step 1: Solve the recurrence for $T_2\left(n\right)$
The recurrence relation for $T_2\left(n\right)$ is given by:
$$T_2\left(n\right)=5T_2\left(\frac{n}{4}\right)+\Theta \left({\log }_{2}n\right)$$
We can solve this using the Master Theorem, which has the general form:
$$T\left(n\right)=aT\left(\frac{n}{b}\right)+f\left(n\right)$$
For $T_2\left(n\right)$, we have:
• $a=5$
• $b=4$
• $f\left(n\right)=\Theta \left({\log }_{2}n\right)$
Now, we compare $f\left(n\right)$ with $n^{{\log }_{b}a}=n^{{\log }_{4}5}$.
Since ${\log }_{4}5\approx 1.161$, we have $n^{{\log }_{4}5}\approx n^{1.161}$.
Clearly, $f\left(n\right)=O\left({\log }_{2}n\right)$ grows much slower than $n^{{\log }_{4}5}$. Formally, $f\left(n\right)=O\left(n^{{\log }_{4}5-\epsilon }\right)$ for any $0<\epsilon \le 0.16$.
By Case 1 of the Master Theorem, the recurrence is dominated by the leaf level, yielding:
$$T_2\left(n\right)=\Theta \left(n^{{\log }_{4}5}\right)$$

Step 2: Solve the recurrence for $T_1\left(n\right)$
Now, substitute the asymptotic behavior of $T_2\left(n\right)$ into the recurrence relation for $T_1\left(n\right)$:
$$T_1\left(n\right)=4T_1\left(\frac{n}{2}\right)+\Theta \left(n^{{\log }_{4}5}\right)$$
Applying the Master Theorem again:
• $a=4$
• $b=2$
• $f\left(n\right)=\Theta \left(n^{{\log }_{4}5}\right)$
Now we calculate $n^{{\log }_{b}a}=n^{{\log }_{2}4}=n^2$.
We compare the exponent of $f\left(n\right)$ which is ${\log }_{4}5\approx 1.161$ with the exponent $2$.
Since $1.161<2$, we have $f\left(n\right)=O\left(n^{2-\epsilon }\right)$ for a positive constant $\epsilon$ (such as $\epsilon \approx 0.839$).
Once again, by Case 1 of the Master Theorem, the recurrence is dominated by the leaf cost:
$$T_1\left(n\right)=\Theta \left(n^2\right)$$