Discussion
The time complexity of recurrence relation \(T(n) = T(n/3) + T(2n/3) + O(n)\) is
Answer: C
The recurrence \(T(n) = T(n/3) + T(2n/3) + O(n)\) has the solution \(O(n \lg n)\). In the recursion tree each level does at most cn work in total, since the sizes n/3 and 2n/3 add up to n. The longest path shrinks by the factor 2/3 each step, so the depth is about \(\log_{3/2} n\).
\[ T(n) = O(cn \cdot \log_{3/2} n) = O(n \lg n) \]
The options \(O(\lg n)\) and \(O(n)\) ignore the work done at each of the levels, and \(O(n^{2})\) is an overestimate.
No comment is present. Be the first to comment.
Loading…
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