0

I am trying to solve $T(n)=T(\frac{n}{2}) + T(\frac{n}{3}) +n $ where n is integer and we want to find the aproximate running time Θ of the tree $T(n)$ where $T(1)=Θ(1)$, At the first level the sum is $n$ at the second it is $\frac{5}{6}n$ at the third $(\frac{5}{6})^2n$ and etc.The tree of the problem can be bounded by 2 trees $S_{1}$ and $S_{2}$. or in other words $S_{1} \le T(n) \le S_{2} $ The sum for first is $ \sum \limits_{n = 1}^{ log_2n} (\frac{5}{6})^in $

and The sum for second is $ \sum \limits_{n = 1}^{ log_3n} (\frac{5}{6})^in $.

But how can I find the Θ of $T(n)$.I think the answer should be $Θ( \sum \limits_{n = 1}^{ log_3n} (\frac{5}{6})^in ) $. but how should I simplify this sum? I was thinking since $Θ( \sum \limits_{n = 1}^{ log_3n} (\frac{5}{6})^in ) $ $\le $ $Θ( \sum \limits_{n = 1}^{ infinity} (\frac{5}{6})^in ) $ =5n then the answer is $ Θ(5n) =Θ(n)$

Joel Separ
  • 1
  • 1
  • does $n$ have to be an integer? Perhaps not, what is $T(1)$ ? May have something to do with geometric series (under the additional assumption that $T$ is continuous at $0$), like $T(1)=T(\frac12)+T(\frac13)+1 = T(\frac14)+T(\frac16)+\frac12+T(\frac16)+T(\frac19)+\frac13 + 1=...$ , ... or am I totally off as to what you are asking? I could only see that $T(0)=T(0)+T(0)+0$, hence $T(0)=0$. – Mirko Apr 24 '17 at 02:35
  • You could try substituting $n = \log{(m)}$, and after you solve the recurrence, use $m=e^n$ to find the solution to the original recurrence in terms of $n$. – Matt Groff Apr 24 '17 at 03:30
  • @MattGroff can you post it as a solution,because I can't see the direction of solving it by this method ,thanks. – Joel Separ Apr 24 '17 at 03:35
  • If you believe $T(n)$ is proportional to $n$ you can substitute $T(n)=kn$ into the recurrence and find $k=6$ is a solution. – Ross Millikan Apr 24 '17 at 03:43

0 Answers0