Consider the following recurrence relation:
\[T(n) = \begin{cases} \sqrt{n}\,T\left(\sqrt{n}\right) + n & \text{for } n \ge 1, \\ 1 & \text{for } n = 1. \end{cases}\]
Which one of the following options is CORRECT?
Answer
(A)
Explanation
Divide both sides by \(n\): \(\frac{T(n)}{n} = \frac{T(\sqrt{n})}{\sqrt{n}} + 1\). Writing \(S(n) = T(n)/n\), this is \(S(n) = S(\sqrt{n}) + 1\): each step takes a square root and adds 1.
For \(n = 2^{2^{k}}\), taking the square root \(k\) times brings \(n\) down to a constant, so \(S(n) = \Theta(k) = \Theta(\log \log n)\) and \(T(n) = n\,S(n) = \Theta(n \log \log n)\).
In the recursion tree, every level does exactly \(n\) work in total (for example \(\sqrt{n}\) subproblems of size \(\sqrt{n}\) cost \(\sqrt{n} \cdot \sqrt{n}\)), and there are \(\log \log n\) levels.
Answer: A