相关疑难解决方法(0)

我一直在看这个重复,并想检查我是否采取了正确的方法.

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)的θ界限

开始学习算法.我理解如何从'常规复发'中找到theta-notation T(n) = Tf(n) + g(n).但是我对这种复发感到迷茫:问题1-2e:

T(n)= T(√n)+Θ(lg lg n)

如何选择找到theta的方法？什么,呃,这种复发是什么？我只是不太明白符号 - 内部复发的事情.

我想解决以下重现关系:

T(n)= 2T(√n);

我猜T(n) = O(log log n),但我不知道如何证明这一点.我如何证明这种复发可以解决O(log log n)？