如何使用替换法解决以下递归问题？

Question

我需要使用替换方法证明以下递归的紧界：

T(n) = 2T(n/2) + n/log(n)

我已经到达替换方法的 "guess" 部分，并且通过使用递归树和迭代方法知道 T(n) 是 O(n*log(log(n)))。但是我很难弄清楚如何从 big-O 和 Omega 的归纳步骤开始：

Assume  T(n/2) <= c*(n/2)log(log(n/2))
T(n) = 2T(n/2) + n/log(n) <= 2c*(n/2)log(log(n/2)) + n/log(n)

Assume  T(n/2) => c*(n/2)log(log(n/2))
T(n) = 2T(n/2) + n/log(n) => 2c*(n/2)log(log(n/2)) + n/log(n)

Answer 1

假设

T(n/2) <= (n/2) log log (n/2) = (n/2) log (log n - 1).

然后

T(n) = 2T(n/2) + n/log n
     <= n log (log n - 1) + n/log n
     = n log log n - n (log log n - log (log n - 1) + 1/log n),

所以足以证明 log log n - log (log n - 1) >= 1/log n 是一般不等式 log k - log (k - 1) >= 1/k 的一个实例，通过将 1/x 从 x = k - 1 积分到 x = k 并应用中值定理。（从视觉上看，一个宽 1 高 1/k 的矩形正好位于 1/x 从 x = k - 1 到 x = k 的曲线下方。）

下界类似；对 k >= 2.

使用不等式 log k - log (k - 1) <= 1/(k - 1) <= 2/k

如何使用替换法解决以下递归问题？

How to solve the following recurrence using the substitution method?

algorithm

recurrence