Я наблюдал за этим повторением и хотел проверить, правильный ли подход я выбрал.
T(n) = T(n^(1/2)) + 1
= T(n^(1/4)) + 1 + 1
= T(n^(1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (a total of rad n times)
= n^(1/2)
Таким образом, ответ придет к тета-границе n ^ (1/2)
Подсказка: предположим, что n = 22m или m = log2log2 n, и вы знаете, что 22m-1 * 22m-1 = 22 m поэтому, если вы определите S(m)=T(n), ваше S будет:
S(m) = S(m-1)+1 S(m) = (m) S(m)=T(n) = (log2log2 н)
распространить его на общий случай.
В рекурсии типа T(n) = T(n/2) + 1 на каждой итерации мы уменьшаем высоту дерева вдвое. Это приводит к (logn). В этом случае, однако, мы делим входное число на степень двойки (а не на двойку), так что получается (log log n).
Вот как вы можете найти ответ без каких-либо подсказок, просто используя математику.
Начните разворачивать рекурсию: 
Рекурсия в какой-то момент остановится, поэтому нам нужно найти разумную точку остановки. Попробовав 0, 1, 2, вы увидите, что 2 выглядит хорошо, потому что вы можете легко решить уравнение: 
.
Решая ее, вы получаете 
Таким образом, рекурсия будет продолжаться log(log(n)) раз, и это ваша временная сложность.
P.S. немного сложнее повторение было решено здесь.
