Solving recurrence equation without the Master's Theorem

Question

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!

Monday

I'm voting to close this question as off-topic because it's not about programming – Overplus

Answer 1

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.

Marlow

Oh, the expansion makes so much more sense now, thanks! However, I'm still stuck on how you can assume T(1)=1. – Monday

It's a reasonable assumption since the algorithm in question will likely run in constant time for that case, i.e. T(1) = O(1). – Marlow

Ah, yeah, that seems reasonable. So, can you just make that assumption for most recurrence relations? – Monday

Unless another base case is specified in the problem, I think this assumption is fine. – Marlow