Как решить T (n) = T (0,2 * n^0,5) + 1?

Question

Я знаю, как решить T(n) = T(n^0.5) + 1. Пусть m = lg n и S(m) = T(2^m). Затем мы получаем S(m) = S(m/2) + 1. И мы знаем S(m) = Θ(lg m). Итак, T(n) = Θ(lg lg n).

Однако я не уверен, как решить T(n) = T(0.2*n^0.5) + 1. 0.2 отбрасывает меня. Если я использую тот же метод, я не уверен, как определить, что такое S(m).

Answer 1

На новой, вы получите

S(lg n) = S(lg 0.2 + 0.5 lg n) + 1 
S(m) = S(lg 0.2 + 0.5 m) + 1. 

Хитрость заключается в том, чтобы заменить R(x) = S(m + 2 lg 0.2).

R(x) = S(m + 2 lg 0.2) 
    = S(lg 0.2 + 0.5 (m + 2 lg 0.2)) + 1 
    = S(0.5 m + 2 lg 0.2) + 1 
    = R(0.5 x) + 1 

Затем распутать замены и заключить, что T(n) = Theta(lg lg n), как и раньше.