Solving recurrence equation without the Master's Theorem
big-o, master-theorem, recurrence
Solution
The trick is to keep expanding until you see the pattern.
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
This keeps going until k is such that 3^k = n.
Assuming `T(1)=1`, you get `T(n) = n^2 +kn^2 = n^2 + log_3(n) n^2`.
So it looks like `T(n) = O(n^2 logn)`, unless I have made an error.
Problem
So, on a previous exam, I was asked to solve the following recurrence equation without using the Master Theorem: ``` T(n)= 9T(n/3) + n^2 ``` Unfortunately, I couldn't figure it out on the exam, so I used solved it using the Master's Theorem just so I could know the answer (but, of course, I got no credit for the question), and now I would like to know how to solve it without the master's theorem since on the final exam, there will be similar questions. If someone could provide a step by step solution (with explanation), that would be brilliant, thanks!