Основная теорема и повторение

Question

Мне дают рецидив T(n) = 3T(n/2) + n^2 lg(n)

Можно ли использовать основную теорему, чтобы найти T(n) = theta(f(n))? Существует полилогарифмическая функция как f (n), но, как я понимаю, есть ограниченный 4-й случай. Подойдет ли этот 4-й случай здесь?

Answer 1

Теорема магистра не имеет никаких ограничений в отношении функции a f(n):

Таким образом, ваш a = 3, b = 2, поэтому c = log2(3), и вы попадаете в третий случай, и решение O(n^2 log n)