Как решить следующую рекурсию с использованием метода подстановки?

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 и применения теоремы о среднем значении. (Визуально, прямоугольник шириной и высотой 11/k подходит под кривой 1/x от x = k - 1 к x = k.)

Нижняя граница аналогична; используйте неравенство log k - log (k - 1) <= 1/(k - 1) <= 2/k для k >= 2.