如何使用替代方法解決以下復發問題？

Question

我需要用替換法來證明以下復發緊約束：

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

我已經抵達的替代方法的「猜測」的一部分，並且知道T(n)是O(n*log(log(n)))使用遞歸樹和迭代方法。但我有麻煩搞清楚如何從爲大O和歐米茄歸納步進行：

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。