对数 T(n) = T(logn)+log(log(n)) 的递归

Question

如何找到递归T(n) = T(logn)+log(log(n))的T(n)=Θ(f(n))？

我认为 T(n)= Θ(log(n)) 但证明对我来说是困难的部分。我将尝试通过替代来证明，但请帮助我。我还尝试了归纳法证明，但很快就失控了...

假设 T(n) = logn 使得

大o证明：

T(n+1) = T(log(n+1))+loglog(n+1)
       = loglog(n+1) + loglog(n+1) < c*log(n) (check)

大欧姆的证明：

T(n-1) = T(log(n-1))+loglog(n-1)
       = loglog(n-1) + loglog(n-1) > c*log(n) (not good)

关于通过 sub 证明这一点的想法。还是通过感应？ ...希望我能插入主定理 ~

Answer 1

直接方法似乎最合适。

T (n) = log log n + T (log n) =
        log log n + log log log n + T (log log n) =
        log log n + log log log n + log log log log n + T (log log log n) =
        log log n + log log log n + log log log log n + log log log log log n + ...

第一个词是log log n，每个词支配下一个词。
所以函数是Omega (log log n).

对数 T(n) = T(logn)+log(log(n)) 的递归

Recurrence with logs T(n) = T(logn)+log(log(n))

algorithm

recurrence

proof

substitution

induction