Я пробовал это в течение многих часов, и я продолжаю прибывать в log (logn) (где log - база 2), но это не согласитесь с теоремой Мастера, которая утверждает, что это будет просто log (n).Найти theta of: T (n) = T (n^(1/2)) + 1
Теорема Мастера здесь не применима, так как мы не делим вход на константу на каждом шаге. Ваш ответ правильный.
Чтобы применить основную теорему, на каждом шаге мы должны делить на константу. Мы все еще можем использовать его в этом случае, но мы должны преобразовать проблему.
Да k=log n, где логарифм находится в основе b и задает S(k)=T(b^k). Затем S(k)=T(b^k)=T(n)=T(n^{1/2})+1=T((b^k)^{1/2})+1=T(b^{k/2})+1=S(k/2)+1, и мы можем применить теорему Мастера к S, которая сообщает нам, что S(k)=Theta(log k). Поэтому, T(n)=T(b^{log n})=S(log n)=Theta(log(log n)), как вы нашли.
Люди правильно предположили, что теорема мастеров здесь не работает. Чтобы решить вашу проблему, вы должны начать разворачивать рекурсию: 
.
Рекурсия в какой-то момент остановится, поэтому нам нужно найти разумную точку остановки. Попытка 0, 1, 2, вы можете видеть, что 2 выглядит хорошо, потому что вы можете легко решить уравнение: 
.
Решив его, вы получите 
.
Таким образом, рекурсия будет продолжаться log(log(n)) раз, и это ваша сложность.
P.S. немного реже было решено here.