Решая рекуррентное уравнение без теоремы Мастера

Question

Итак, на предыдущем экзамене, мне было предложено решить следующее рекуррентное уравнение без использования Master теорему:

T(n)= 9T(n/3) + n^2 

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

Если кто-то может предоставить пошаговое решение (с объяснением), это было бы великолепно, спасибо!

Answer 1

Трюк состоит в том, чтобы продолжать расширяться, пока вы не увидите рисунок.

T(n) 
= 9 T(n/3) + n^2 = 9(9T(n/3^2) + n^2/3^2) + n^2 
= 9^2 T(n/3^2) + 2n^2 = 9^2 (9 T(n/3^3) + n^2/3^4) + 2n^2 
= 9^3 T(n/3^3) + 3n^2 
= ... 
= 9^k T(n/3^k) + kn^2 

Это продолжается до тех пор, пока k не будет таким, чтобы 3^k = n. Предполагая, что T(1)=1, вы получаете

T(n) = n^2 +kn^2 = n^2 + log_3(n) n^2.

, поэтому он выглядит как T(n) = O(n^2 logn), если только я не сделал ошибку.