When n = 22k for some k ≥ 0, the recurrence relation T(n) = √(2) T(n/2) + √n,…

Key idea: use a recursion tree and compare n^{log_b a} with f(n).

Details:

• Here a = √2 and b = 2, so n^{log_b a} = n^{log_2 √2} = n^{1/2} = √n.

• The additive term is f(n) = √n, which matches n^{log_b a}, so this is the regularity (balanced) case of the master theorem.

• Recursion-tree perspective: at level i there are (√2)^i subproblems, each contributing √(n/2^i) = √n / 2^{i/2}. The level contribution is

• (√2)^i · (√n / 2^{i/2}) = √n · (2^{i/2} / 2^{i/2}) = √n.

• There are log_2 n + 1 levels (i = 0 through log_2 n), so summing contributions gives √n · (log n + 1).

• Including the leaf costs (T(1)=1) yields the same √n contribution at the last level, already counted above.

Final result: T(n) = √n · (log n + 1), which is Θ(√n · log n).