recurrence relations substitution method

Question

Hi any one knows the approach to solve this recurrence: $T(n)=3T(\frac{n}{3}- 2)+ \frac{n}{2}$; Master method not suitable. Then how the substitution can be done to find the bound?

Answer 1

The non-canonical part of this recursion is the argument $\frac{n}3-2$ in the RHS. To deal with it, note that if $n=3^k-3$ then $\frac{n}3-2=3^{k-1}-3$. Hence $S(k)=T(3^k-3)$ is such that $$ S(k)=3S(k-1)+\tfrac12(3^k-3), $$ and one is in known territory again. A direct way to solve the recursion involving $(S(k))$ is to consider $R(k)=2\cdot3^{-k}\cdot S(k)$, then $R(k)=R(k-1)+1-\frac1{3^{k-1}}$ hence $R(k)=k+O(1)$. This yields $$ T(3^k-3)=\tfrac12k3^k+O(3^{k}). $$ which can be summarized as $$ T(n)\sim\tfrac12n\log_3n. $$