Induction Proof $T(n) = 9T(n/3) + n^2$

1
votes

How can I prove that the reccurence

T(n) = 9T(n/3) + n2

leads to T(n) = O(n2 log(n)) using the substitution method and a proof by induction? I’m not allowed to use the Master Theorem.

Using induction and assuming T(n) ≤ cn2 log n, I got to the following point:

T(n) = 9 * T(n/3) + n2

≤ 9c ( n2 / 9 + log(n/3)) +n2

= cn2 + 9c log(n/3) + n2

Thank you.

1
mathrecurrenceproofinduction
Are you allowed to use the Master Theorem here? - templatetypedef
No, i have to Proof by induction - Joshua
What are the policies for the class that you’re taking? Are you allowed to ask questions on Stack Overflow? - templatetypedef
Yes, its even recommended - Joshua
Can you show your intermediate work that got you to the inequality you came up with above? - templatetypedef

1 Answers

1
votes

I think you've made a math error in your substitution. If we assume that T(n) ≤ cn2 log n, then we'd get

T(n) = 9T(n / 3) + n2

≤ 9(c(n / 3)2 log(n / 3)) + n2

= 9((1 / 9)cn2 log (n / 3)) + n2

= cn2 log(n / 3) + n2

You're very close to having things complete at this point. As a hint, suppose that the logarithm is a base-3 logarithm. What happens if you then use properties of logarithms to simplify cn2 log(n / 3)?