# Can't solve a recurrence

I am trying to solve the following recurrence:

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

If I use the master method, I get $n^2\log{n}$

But, I am trying to solve it using substitution. When I try solving it this way, however, I run into trouble. After I roll out the substitution for a few times, I get the following formula:

$$T(n) = 9^kT(n/3^k)+n^2\sum_{i=1}^k3^{j-1}$$

I've tried to simplify the summation several ways, but I don't think I am understanding what the next step should be. When I simplify the problem, I keep getting the wrong answer. I know I should eventually set $k$ to be equal to some logarithm so I an reach the base case for T, but right now my main issue it figuring out how to simplify the summation. I am quite bad at simplifying summations, so any detailed steps are greatly appreciated.

• Corrected! you can just take $k=log_3(n)$ and you can get $T(n)=n^2T(1)+n^2log_3(n)$ which is true for every element of $n$ of the form $n=3^K$. this is if you'are trying to find the complexity of your algorithm, and if you want to be more precise maybe you need to define $T(a)$ for an integer which is not divisible by $3$ and you can see also this post :math.stackexchange.com/questions/601295/… – Elaqqad Mar 2 '15 at 20:53
• Actually, they are not. $3^k = n$ so you get $O(n^3)$. – Qudit Mar 2 '15 at 20:56
• I think it's $O(n^2log(n))$ – Elaqqad Mar 2 '15 at 20:59
• No, $n^2 3^{\log_3 n - 1}$ is not $O(n^2 \log n)$. – Qudit Mar 2 '15 at 21:01

Your summation is wrong. It should be

$$T(n) = 9^k T(n / 3^k)+ \sum_{i=1}^k n^2$$

This is because $(n / 3^k)^2 = n^2 / 9^k$ so you get cancellations.

• I don't see how that summation will work. If you expand out the recurrence as you substitute up to k=3 for example you will get: $$9^3T(n/3^3) + 9n^2 + 3n^2 + n^2$$ How are you accounting for the 9 the 3 and 1 in front of the $n^2$? I guess I just don't see what $n^2$ is inside the summation. You can pull it out. – SherMM Mar 2 '15 at 21:04
• Try writing out the expansion step by step and you should get the equation above. – Qudit Mar 2 '15 at 21:08
• I've written out the expansion multiple times, and I still get what I wrote in the comment above. I don't understand where you got that summation formula. If I have $9n^2 + 3n^2 + n^2$ above, then the general pattern for that part of the equation that I see is $$n^2\sum_{i=0}^k3^j$$ I don't see my mistake. – SherMM Mar 2 '15 at 21:17
• It sounds like you put one less three in the denominator than you should have after squaring. It would be easier to explain if you posted your work in getting that expansion. – Qudit Mar 2 '15 at 21:24
• I start with $$T(n) = 9T(n/3) + n^2 = 9(9T(n/9) + n^2/3) + n^2 = 9^2T(n/9)+3n^2+n^2= 9^2(9T(n/27)+n^2/9)+3n^2+n^2......$$ – SherMM Mar 2 '15 at 21:31

The summation seems particularly "nice" if $n$ is a power of $3$, so lets assume $n=3^k$, then $$T(3^k)=3^2T(3^{k-1})+3^{2k}$$ and $$T(3^{k-1})=3^2T(3^{k-2})+3^{2k-2}$$ So by susbstitution: $$T(3^k)=3^2(3^2T(3^{k-2})+3^{2k-2})+3^{2k}=3^4T(3^{k-2})+2*3^{2k}$$ Now, $$T(3^{k-2})=3^2T(3^{k-3})+3^{2k-4}$$So $$T(3^k)=3^4(3^2T(3^{k-3})+3^{2k-4})+2*3^{2k}=3^6T(3^{k-3})+3*3^{2k}$$ In general $$T(3^k)=3^{2a}T(3^{k-a})+a*3^{2k}$$ for any natrual $a$ (can be easily verified via induction), so if we set $a=k$, we get $$T(3^k)=3^{2k}T(1)+k*3^{2k}$$ Now by backwards substituting $k=\log_3(n)$, we get that $$T(n)=n^2T(1)+n^2\log_3(n)$$

$$T(n)-9T(n/3)=n^2$$ $$9^kT(n)-9^{k+1}T(n/3)=9^kn^2$$ $$9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2$$ $$\sum_{k=0}^{\lfloor{\log_3(n)}\rfloor}9^kT(n/3^k)-9^{k+1}T(n/3^{k+1})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)-9T(n/3)+9T(n/3)-9^2T(n/3^2)+....-9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})=n^2(\lfloor{\log_3(n)}\rfloor+1)$$ $$T(n)=n^2(\lfloor{\log_3(n)}\rfloor+1)+9^{\lfloor{\log_3(n)}\rfloor}T(n/3^{\lfloor{\log_3(n)}\rfloor})$$ $$=n^2\log_3(n)+O(n^2T(n/3^{\lfloor{\log_3(n)}\rfloor}))$$ $$=n^2\log_3(n)+O(n^2T(c))$$ $$\text{Where } 0<c<3$$