algorithm - 对数 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)。