Без использования основной теоремы, просто продолжайте расширять рекуррентное отношение, пока не увидите шаблон.
T(n) = 4T(n/2) + Θ(n^2 /log(n))
= 4*(4t(n/4) + theta((n/2)^2 / log(n/2))) + theta(n^2/log(n))
= 4^2 * (t(n/4) + theta((n/2)^2 / log(n/2)) / 4) + theta(n^2/log(n))
theta((n/2)^2 / log(n/2)) / 4 can be simplified to theta(n^2/log(n))
= 4^2 * (t(n/4)) + 2theta(n^2/log(n))
= 4^2 * (4t(n/8) + theta((n/4)^2 / log(n/4))) + 2theta(n^2/log(n))
= 4^3 * (t(n/8) + theta((n/4)^2 / log(n/4)) / 4) + 2theta(n^2/log(n))
theta((n/4)^2 / log(n/4)) / 4 can be simplified to theta(n^2/log(n))
= 4^3 * (t(n/8)) + 3theta(n^2/log(n))
Так что мы можем еще больше упростить это до
4^k * (t(n/k)) + k*theta(n^2/log(n))
Это будет продолжатьсяпока k = n и, предполагая, что T (1) = 1, мы получим
4^n + n*theta(n^2/log(n))
И, поскольку 4 ^ n больше, чем n * theta (n ^ 2 / log (n)), ответ O (4 ^ п) .