computer-science - T(n-1) + 1/lg(n) 重复

Question

我正在寻找一个上限和下限（或者只是一个 theta 界限，就此而言）。

T(n) = T(n-1) + 1/lg(n)

我正在为考试而学习，这是我一直坚持的练习题之一。

Answer 1

我想下面的扩展会给你适当的提示：

T(n) =

= 1/lg(n) + T(n-1)

= 1/lg(n) + 1/lg(n-1) + T(n-2)

= 1/lg(n) + 1/lg(n-1) + 1/lg(n-2) + T(n-3)

=···

= 1/lg(n) + ··· + 1/lg(n/2) + T(n/2)

= Theta(n/lg(n)) + T(n/2)

现在，在这个新的递归上使用 Master 定理。