Решить рекуррентное соотношение по основной теореме

Question

Меня смущает, какой случай основной теоремы находит жесткую оценку для этого рекуррентного отношения:

T (n) = 27T (n / 3) + Q (n ³ log n)

Вот мое решение:
f (n) = n ³ log n
a = 27 b = 3, поэтому

Итак, мы можем видеть здесь, что f (n)> n ³
Итак, это:

Случай 3 будет применяться: поправьте меня, если я ошибаюсь здесь.
Примечание: Но ответ приходит n ³ log ² n, который наступает в случае 2 основной теоремы,Который я должен применить?

Answer 1

Проверьте это:

http://en.wikipedia.org/wiki/Master_theorem#Case_2

И если у вас есть третье издание CLRS: см. Вопрос 4.6-3

Вы должны быть в состоянии получить этоследуя Доказательству основной теоремы, а затем подставляя форму f (n).