2

$T(1) = 1$

$T(n) = 2T(\frac{n}{3}) + n + 1$

How do you solve this equzione recurrence? I arrived at this point and then I don't know how to proceed...

$2^kT(\frac{n}{3^k}) + \frac{2^{k-1}n}{3^{k-1}} + 2^{k-1} + \frac{2^{k-2}n}{3^{k-2}} + 2^{k-2} + \frac{2n}{3} + 2 + 1$

Thanks a lot!

Katherine Maurus
  • 199
  • 1
  • 9
  • Are you looking for a closed form? or just asymptotically tight bounds? – TravisJ Jun 02 '15 at 14:43
  • @TravisJ I would like to get to the asymptotic solution. – Katherine Maurus Jun 02 '15 at 14:56
  • @Barry, already gave a solution. Let me just point out that you are essentially already there. Note that $T(\frac{n}{3^{k}})=T(1)$ once $3^{k}\approx n$. So the algorithm iterates until $k=\log_{3}(n)$. Your first term is $2^{\log_3(n)}$... using the value of $k$ you can see what each of those terms are. the $2n/3$ turns out to be the major term, so you have $T(n)=\Theta(n)$. – TravisJ Jun 02 '15 at 15:04

1 Answers1

0

Use the Master Method:

$T(n) = 2T(\frac{n}3) + n + 1$ falls into Case 3, because $c > \log_{b}(a)$, with $c=1$, $a=2$, $b=3$, $f(n) = n+1$. Additionally $af(\frac{n}{b}) \leq kf(n)$ is trivially satisfied with $k = \frac{2}{3}$.

Thus, $T(n) = \Theta(f(n)) = \Theta(n)$.

Barry
  • 2,268
  • I had a doubt. Since the Master Theorem I studied using this formula $T(n) = aT(n/b) + cn^s$, can I apply the theorem even in cases like $T(n) = 2T(n/3) + n^2 + 1$ and then consider $cn^s$ as $n^2$ (ignoring $1$)? – Katherine Maurus Jun 02 '15 at 19:56
  • @user3808470 That's the wrong formula. Should be $f(n)$ at the end. – Barry Jun 02 '15 at 20:04
  • Thanks, so my reasoning is wrong? Can I consider $f(n) = n^2 + 1$? And then? Sorry but it seemed simple to me to use it and instead... – Katherine Maurus Jun 02 '15 at 20:14
  • @user3808470 Yes you can. So $c=2 > \log_b{a}$, so we're still in case 3. Regularity checks out, so we're fine there. So just $T(n) = \Theta(f(n)) = \Theta(n^2)$ – Barry Jun 02 '15 at 20:32