computer-science - T（n-1）+ 1 / lg（n）の再発

Question

私は上界と下界（または、さらに言えば、シータ境界）を探しています。

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

私はテストのために勉強しています、そしてこれは私が立ち往生している練習の質問の1つです。

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)

= シータ(n/lg(n)) + T(n/2)

ここで、この新しい再帰についてマスター定理を使用します。