Класс сложности рекуррентного уравнения

Question

Это было для меня какое-то время с моего курса по алгоритму. Не могли бы вы помочь мне решить это рекуррентное уравнение?

T(0)=14
T(n)=4*T(n/2)+n^2 for n>0

Меня интересует верхняя граница, которая как можно ниже.

Answer 1

Точное решение этого уравнения трудно вычислить, но, согласно основной теореме, это асимптотика c предел равен Θ (n ² log n)

РЕДАКТИРОВАТЬ 1:

На самом деле можно вычислить точное решение, оно (для n> 0)

n ² (228 log (2) +4 log (n)) / log (16)

(я получил это решение, по возможности добавляя константы к решению основной теоремы и решая систему из 5 уравнений с применением компьютерной алгебры)

Answer 2

Если n - это степень 2, а n> 0 , то следующее выражение дает решение:

(57 + log ₂ п) n²