Рецидив решение подстановкой

Question

T(n) = { 0      If n = 0 
     { T(square root n) + 1 If n > 0 

Я пытаюсь решить, что с помощью замены

Мое предположение: O(lg lg n)

С помощью индукции

T(n) = c lg lg n 
T(n) =< c (lg lg square root n) + 1 

С square root n = n^1/2 =< c(1/2 lg lg n) + 1

Я не в состоянии продолжить эту часть, чтобы получить lg lg n, и я видел много решений, которые используют полномочия. Есть ли другой способ?

Можно ли рисовать дерево рекурсии, чтобы помочь мне разобраться?

1 
|| 
n^1/2 
|| 
n^1/4 
|| 
n^1/8 

T(n) = 1 + ....... 

Answer 1

Самый простой способ понять это с полномочием 2, как и многих других ответов говорит, но, чтобы продолжить шаг вы упомянули, предположит T(n) = lg lg n (без учета постоянная, как это точный ответ).

Тогда мы имеем:

T(sqrt(n)) = lg lg (sqrt(n)) = lg (1/2 * lg (n)) 
= lg (2^(-1) * lg(n)) 
= -1 + lg lg (n) 
= -1 + T(n) 

Итак, как вы видите, T(n) = T(sqrt(n)) + 1