Рассчитать временную сложность отношения повторяемости, обозначение Big-Oh

Question

Я пытаюсь найти Big-Oh этого отношения повторения: T (N) = 4T (N / 2) + N ^ 2.

T (1) = 1

Answer 1

Из основной теоремы можно сказать, что T (n) = \ Theta (N ^ 2 log (N)) (см. Случай 2).

Answer 2

Ответ рекуррентного отношения: O (N ^ 2 log N)