Consider the following recurrence relation: \(T(n) = \begin{cases} \sqrt{n}…

Short answer: T(n) = Θ(n log log n)

Proof idea: substitute n = 2^m and analyze a scaled function to simplify the recurrence.

1. Define m so that n = 2^m, and define S(m) = T(2^m)/2^m.

2. Rewrite the recurrence in terms of S:

   T(2^m) = 2^{m/2} T(2^{m/2}) + 2^m. Dividing both sides by 2^m gives

   S(m) = T(2^m)/2^m = T(2^{m/2})/2^{m/2} + 1 = S(m/2) + 1.

3. Solve S(m) = S(m/2) + 1. Repeated substitution adds 1 at each level until m reaches the base (m = 0), so the number of additions is Θ(log m). Therefore S(m) = Θ(log m).

4. Translate back to n: m = log_2 n, so S(m) = Θ(log log n). Hence T(n) = 2^m S(m) = n · Θ(log log n) = Θ(n log log n).

This matches the correct option.