Discussion
Consider the following recurrence relation:
\[ T(n) = \begin{cases} \sqrt{n}\,T(\sqrt{n}) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases} \]
Which one of the following options is CORRECT?
Answer: A
\(T(n) = \Theta(n \log \log n)\).
Divide the recurrence by n and set \(S(n) = T(n)/n\):
\[ \begin{aligned} \frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 \\ S(n) &= S(\sqrt{n}) + 1 \end{aligned} \]
Each step takes a square root, and n reaches a constant after \(\log \log n\) square roots (write \(n = 2^{2^{k}}\); each step halves k). So \(S(n) = \Theta(\log \log n)\) and \(T(n) = \Theta(n \log \log n)\). \(n \log n\) would come from halving n at each level instead of square-rooting it, and the \(n^{2}\) options overcount the work per level, which is n at every level of the recursion.
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