Discussion
Consider the following recurrence relations:
For all \(n \gt 1\),
\[ \begin{aligned} 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) \end{aligned} \]
Assume that for all \(n \le 1\), \(T_{1}(n) = 1\) and \(T_{2}(n) = 1\).
Which one of the following options is correct?
Answer: A
The answer is \(T_{1}(n) = \Theta(n^{2})\).
Solve the inner recurrence first with the master theorem. For \(T_{2}\), a = 5 and b = 4, so \(n^{\log_{4} 5} \approx n^{1.16}\), which grows faster than \(\log_{2} n\):
\[ T_{2}(n) = \Theta(n^{\log_{4} 5}) \]
For \(T_{1}\), a = 4 and b = 2, so the leaves contribute \(n^{\log_{2} 4} = n^{2}\). The added term \(T_{2}(n) = \Theta(n^{1.16})\) is polynomially smaller than \(n^{2}\), so the first case applies:
\[ T_{1}(n) = \Theta(n^{2}) \]
The extra \(\log_{2} n\) factor would appear only if the added term were \(\Theta(n^{2})\). The options with \(n^{\log_{4} 5}\) give the order of \(T_{2}\), not \(T_{1}\).
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development