Применение основной теоремы

Question

Я пытаюсь готовиться к экзаменам, глядя на свои среднесрочные результаты. Одна вещь, которую я не понимаю полностью, это основная теорема. Я понимаю, что есть три случая, и могу применить их, когда они находятся в этой форме

T(n) = 25T(n/5) + n^(2)

но мой профессор любит давать в таком виде

T(n) = {n+2, если n = 0,1,2,3
T (n) = {4T (n-1) - 6T (n-2) + 4T (n-3) - T (n-4) в противном случае

Поэтому я запутался, если есть другой способ сделать основную теорему, или если мне нужно каким-то образом изменить это в формат, который я понимаю.

Answer 1

П ^lg25= п ^2. а в нерекурсивной части мы имеем это. Итак, мы должны mult n^2 *log n. поэтому решение - o(n^2 log n)