我一直在找这个rec​​currence，并要检查，如果我正在采取正确的方法。

I've been looking at this reccurrence and wanted to check if I was taking the right approach.

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)

因此​​，答案会来THETA约束的n ^（1/2）

So the answer would come to theta bound of n^(1/2)

推荐答案

提示：假设N = 2 2 M 或m =日志 2 日志 2 N，你知道2 2 M-1 * 2 2 M-1 = 2 2 M 因此，如果定义S（M）= T（n）的你的旨意是：

hint: assume n = 22m or m = log2log2n, and you know 22m-1 * 22m-1 = 22m so, if you define S(m)=T(n) your S will be:

S（米）= S（M-1）1＆RARR; S（米）=＆的Theta;（米）＆RARR; S（M）= T（N）=西塔（登录 2 日志 2 N）

S(m) = S(m-1)+1 → S(m) = Θ(m) → S(m)=T(n) = Θ(log2log2n)

扩展它的一般情况。

在递归样T（N）= T（N / 2）+ 1，你会减少树高2倍，每次迭代从而导致＆西塔;（LOGN），但在这种情况下，就可以减少输入号的功率两个（不是两次），所以它会与西塔（日志日志N）

In recursion like T(n) = T(n/2) + 1 you will reduce height of tree 2 times in each iteration which leads to Θ(logn) but in this case, you will reduce input number by power of two (not two times) so it will be Θ(log log n ).