0

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?

DanielY
  • 979
studnt
  • 71
  • try to find a returning pattern while solving the function. here: $T(n) = 3T(\frac{n}{3} - 2) + \frac{n}{2} = 3[3T(\frac{n}{9} - 2) + \frac{n}{6}] + \frac{n}{2} = 9T(\frac{n}{9} - 2) + n = ...$ – DanielY Oct 08 '13 at 07:54
  • Can you please elaborate more, I am unable to find the solution. – studnt Oct 08 '13 at 11:50
  • Sorry, I have problem with this type of questions. I can learn if you can please solve it. I didn't get how the terms are modified here? What is the assumption made about the bound to expand it in this way?if any please. – studnt Oct 08 '13 at 14:02
  • I'm not ignoring you on purpose, I try to solve it all the way but the truth is that I'm stuck. I've learnt this material 2 years ago :) – DanielY Oct 09 '13 at 05:30
  • 3T(n/3-2)+n/2; 3[3T(n/9-2)+n/6]+n/2; 9T(n/9-2)+n/2+n/2; 9[3T(n/27-2)+n/18]+n; 27T(n/27-2)+3n/2....Is it following any pattern (if my steps are correct) like 3^kT[(n/3^k-2)+kn/2; ; so the solution will it be something like O(nlog3 n) ? – studnt Oct 09 '13 at 12:07

1 Answers1

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. $$

Did
  • 279,727