Recurrence $k$-th pattern by substitution

48 Views Asked by At

The recurrence is $T(n) = 9 T(\frac{n}{3}) + {n^2}$. Simplified to ${3^2} T(\frac{n}{3}) + {n^2}$. Then

$$\begin{align} T(n)&= 3^4T(\frac{n}{3^2}) + 4n\\ &= 3^6T(\frac{n}{3^3}) + 10n\\ &= 3^8T(\frac{n}{3^4}) + 28 n. \end{align}$$

I am trying to find the $k$-th pattern of this recurrence.

1

There are 1 best solutions below

1
On BEST ANSWER

In my opinion something is wrong in your approach.

If $T(n)={3^2} T(\frac{n}{3}) + {n^2}$, then $T(\frac{n}{3^k})={3^2} T(\frac{n}{3^{k+1}}) + (\frac{n}{3^k})^2$ and $$\begin{align}T(n)&={3^2} T(\frac{n}{3}) + {n^2}={3^2} \left({3^2} T(\frac{n}{3^2}) + \frac{n^2}{3^2}\right) + n^2\\ &={3^4} T(\frac{n}{3^2}) + 2n^2 ={3^4} \left({3^2} T(\frac{n}{3^3}) + \frac{n^2}{3^4}\right) + 2n^2\\ &={3^6} T(\frac{n}{3^3}) + 3n^2=\dots={9^k} T(\frac{n}{3^k}) + kn^2.\\ \end{align}$$

P.S. Do you know the Master Theorem?