Time complexity for the recursive relation T(n) = 2T(√n) + 1 is:

To solve the recurrence T(n) = 2T(sqrt(n)) + 1, use variable substitution. Let n = 2^m, so m = log_2(n). Then sqrt(n) = 2^(m/2). Define S(m) = T(2^m). The recurrence becomes S(m) = 2S(m/2) + 1. By the Master Theorem with a=2, b=2, f(m)=1, we have log_b(a) = 1. Since f(m) is O(m^(1-epsilon)), the solution is S(m) = Theta(m). Substituting back m = log_2(n), the time complexity is T(n) = Theta(log n).