Discussion
The solution of the recurrence relation of \(T(n) = 3T\left(\left\lfloor \frac{n}{4} \right\rfloor\right) + n\) is
Answer: C
The solution is \(O(n)\).
Here \(a = 3\), \(b = 4\), and \(n^{\log_4 3} \approx n^{0.79}\) is smaller than the added work \(f(n) = n\). By case 3 of the master theorem, with the regularity condition \(3(n/4) \le (3/4)n\) holding, \(T(n) = \Theta(n)\), hence \(O(n)\).
\(O(n^{2})\) and \(O(n \lg n)\) are not tight, and \(O(\lg n)\) is too small. Check the master theorem condition: \(f(n) = n = \Omega(n^{0.79 + \epsilon})\) for a small \(\epsilon \gt 0\), and \(3 f(n/4) = 3n/4 \le c f(n)\) with \(c = 3/4 \lt 1\), so case 3 applies and the solution is of the order of \(f(n)\), that is \(n\).
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