To solve the recurrence relation $T(n) = 9T\left(\frac{n}{3}\right) + n\log^2{n}$ using the substitution method, we proceed as follows:

Recurrence Relation

Given: $T(n) = 9T\left(\frac{n}{3}\right) + n\log^2{n}$

Hypothesis for Induction

We assume a solution of the form: $T(n) \leq c n \log_6{9} - c' n (\log^2{n})$ for some constants $c$ and $c'$, and we need to verify this assumption.

Base Case

First, check if this assumption holds for a small value of $n$ (e.g., $n = 1$). Since we're primarily interested in large $n$, the base case is typically straightforward and involves setting $n$ to the smallest value that makes sense in the context of the recurrence (usually $n = 1$ or $n = 3$).

Inductive Step

Assume that the hypothesis holds for some $n \geq 1$, i.e., $T\left(\frac{n}{3}\right) \leq c \cdot \frac{n}{3} \log_6{9} - c' \cdot \frac{n}{3} \log^2{\frac{n}{3}}$

Now substitute this into the recurrence relation: $T(n) = 9T\left(\frac{n}{3}\right) + n\log^2{n}$ $\leq 9 \left( c \cdot \frac{n}{3} \log_6{9} - c' \cdot \frac{n}{3} \log^2{\frac{n}{3}} \right) + n\log^2{n}$ $= 3cn \log_6{9} - 3c'n \log^2{\frac{n}{3}} + n \log^2{n}$

Simplification

Let's simplify $\log^2{\frac{n}{3}}$ using logarithmic properties: $\log{\frac{n}{3}} = \log{n} - \log{3}$ $\log^2{\frac{n}{3}} = (\log{n} - \log{3})^2 = \log^2{n} - 2\log{n}\log{3} + \log^2{3}$

Substitute back: $T(n) \leq 3cn \log_6{9} - 3c'n (\log^2{n} - 2\log{n}\log{3} + \log^2{3}) + n \log^2{n}$ $= 3cn \log_6{9} - 3c'n \log^2{n} + 6c'n\log{n}\log{3} - 3c'n\log^2{3} + n \log^2{n}$

Combine like terms: $T(n) \leq n\log^2{n}(1 - 3c') + 3cn \log_6{9} + 6c'n\log{n}\log{3} - 3c'n\log^2{3}$

Choosing $c$ and $c'$

• To satisfy the recurrence, choose $c' = \frac{1}{3}$, so that $1 - 3c' = 0$ eliminates the negative term.
• The remaining terms should satisfy the original hypothesis: $T(n) \leq n\log^2{n} \times 0 + 3cn \log_6{9} + 6c'n\log{n}\log{3} - 3c'n\log^2{3}$

Thus: $T(n) \leq cn\log_6{9} + O(n\log{n})$

Conclusion

We have shown that for sufficiently large $c$ and appropriate choice of $c'$, the assumed form holds, which leads to the final bound: $T(n) = O(n \log_6{9}) = O(n^2)$ Since $\log_6{9} = \frac{\log{9}}{\log{6}}$, this still gives a polynomial $T(n) = O(n^2)$ as expected.

---

Would you like more details or have any questions about this method?

Here are five related questions that might deepen your understanding:

1. Why is the logarithm base important when analyzing the recurrence relation?
2. How do you handle recurrence relations where $f(n)$ is a non-polynomial function?
3. What is the significance of the constants $c$ and $c'$ in the substitution method?
4. How does the substitution method differ from the Master Theorem in solving recurrences?
5. Can you apply the substitution method to a recurrence relation that results in an exponential function?

Tip: When using the substitution method, it's important to carefully choose the constants in your hypothesis to ensure that the inequality holds true for the entire range of $n$.