Question

Consider the following recurrence relation: \[ T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1,
1 & \text{for } n = 1. \end{cases} \] Which one of the following options is CORRECT?

• A. \( T(n) = \Theta(n \log \log n) \)
• B. \( T(n) = \Theta(n \log n) \)
• C. \( T(n) = \Theta(n^2 \log n) \)
• D. \( T(n) = \Theta(n^2 \log \log n) \)

Hint:

For recurrence relations involving nested square roots, use transformations like ( n = 2^m ) to simplify and determine the number of levels.

Answer 1

The Correct Option is A

Step 1: Recurrence Analysis.
The given recurrence is: \[ T(n) = \sqrt{n}T(\sqrt{n}) + n. \] Let \( n = 2^m \). Then, \( \sqrt{n} = 2^{m/2} \), and the recurrence becomes: \[ T(2^m) = 2^{m/2} T(2^{m/2}) + 2^m. \] Step 2: Substitution.
Substitute \( T(2^m) = f(m) \). The recurrence now becomes: \[ f(m) = 2^{m/2} f(m/2) + 2^m. \] Step 3: Expanding the Recurrence.
Expand the recurrence: \[ f(m) = 2^{m/2} \left( 2^{m/4} f(m/4) + 2^{m/2} \right) + 2^m. \] \[ f(m) = 2^{m/2} \cdot 2^{m/4} f(m/4) + 2^m + 2^m. \] This continues for \( k \) levels, with each level contributing \( 2^m \). The number of levels is approximately \( \log \log n \). Step 4: Complexity.
The total complexity is: \[ T(n) = \Theta(n \log \log n). \] Final Answer: \[ \boxed{\Theta(n \log \log n)} \]