Menu
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!
204
1) Substitution Method: We make a guess for the solution and then we use mathematical induction to prove the guess is correct or incorrect. 2) Recurrence Tree Method: In this method, we draw a recurrence tree and calculate the time taken by every level of the tree. Finally, we sum the work done at all levels.
Recall that we cannot use the Master Theorem if f(n) (the non-recursive cost) is not polynomial. There is a limited 4-th condition of the Master Theorem that allows us to consider polylogarithmic functions.
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.
98
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
