嗨，我正在尝试用主定理解决以下等式：
T（n）= a;对于n <= 2
T（n）= T（√n）+ a;其他
当我发现一个类似的等式（Solving the recurrence T(n) = 2T(sqrt(n))）时，我想知道我的解决方案是否正确。我得到T（n）= O（log log n）。这对我上面的等式是否正确？
我们可以写下一张表并寻找一个模式：
n T(n)
- ----
2 a
4 T(2) + a = 2a
16 T(4) + a = 3a
256 T(16) + a = 4a
...
2^(2^k) (k+1)a
我们注意到2 = 2^(2^0)，4 = 2^(2^1)，16 = 2^(2^2)等等;从两个开始并反复平方，我们得到像2^(2^k)这样的术语，其中T(n)的相应值只是(k+1)a。
鉴于n = 2^(2^k)和T(n) = (k+1)a，我们可以用k解决n的这些方程中的第一个，然后在第二个中替换。我们得到了log log n = k和T(n) = (1 + log log n)a，它具有你所追求的渐近约束。
从技术上讲，为了完成这个论证，我们必须注意T(n)是一个单调非递减函数，因此我们已经证明了函数以这种方式限制了n这个特定的值序列。通常，函数可能会以这样一种方式运行，即上述分析方法可能被欺骗，表明不准确的界限。对于性能良好的功能，通常不会发生这种情况。