Решение повторения с использованием основного метода, когда g (n) = log (n)

Question

Я пытаюсь решить повторение f (n) = 2f (n / 2) + logn, когда f (1) = 1 и n - степень 2. Я думаю, что я должен быть в состоянии сделать это, используя мастер метод. Я видел это раньше, но никогда с журналом. Могу ли я получить помощь, чтобы начать, пожалуйста?

Answer 1

Один из приемов, который часто полезен здесь, - это заменить термин log n чем-то, что растет строго быстрее или медленнее, и посмотреть, что вы получите. Например, ваше повторение ограничено сверху и снизу, соответственно, этими повторениями:

A (n) = 2A (n / 2) + & radic; n.

B (n) = 2A (n / 2) + 1.

Что они решают? Что это говорит вам о вашем повторении?