2

Please explain the most elementary method of solving this recurrence relation: $$ T(n) = 2T\left(\left\lfloor\frac{2n}{3}\right\rfloor\right)$$ where $T(0) = 0$ and $T(1) = 1$.

Will
  • 940
  • 1
    Then why don't you write $\lfloor \dfrac{2n}{3} \rfloor$ instead of $\dfrac{2n}{3}$? –  Jan 30 '12 at 23:11
  • please next time write initial values before anyone answer your question! – Lrrr Jan 31 '12 at 14:23
  • Why write $T(0)=1$? It contradicts your recurrence when $n=1$ and it is never used when $n \ge 2$. – GEdgar Jan 31 '12 at 16:53
  • @GEdgar That was how the problem was stated in the homework question. However, I've edited the question to reflect your observation since you're definitely correct! – Will Jan 31 '12 at 18:42
  • @J.D. Same situation as in the above comment. Thanks for the suggestion! – Will Feb 01 '12 at 00:23

4 Answers4

2

$\bf Hint:$ Note that $T(0)=2T(0)$ so $T(0)=0$. You can compute a few integers to get a pattern and then use induction to show that your guess is correct.

azarel
  • 13,120
2

use azarel's hint and in the end you got : $T(n) = 0$

Edit: the answer was right; but after adding initial value to question my answer is no longer right, since the right answer is posted there is no need I change my answer.

Lrrr
  • 892
2

I'm assuming the "reasonable" interpretation that $T(0)$ is some given constant, say $c$, and $T(n) = 2T(\lfloor 2n/3 \rfloor)$ for $n \ge 1$.

Then my hint is as follows: compute values of $T(n)$ up to, say, $n = 15$, in terms of $c$. There are repeated values. If you write out the sequence $T(0), T(1), T(2), \ldots$ when does the sequence change? (Ayman's hint is useful but perhaps a bit misleading; generalizing from the solution in real numbers to the solution in integers is a bit tricky here.)

Michael Lugo
  • 22,354
1

Hint: If the initial value isn't 0, do the following variable substitution: $ n = \left(\frac{3}{2}\right)^m $

Solve the recurrence. Once done, can you generalize your solution to integers?

Ayman Hourieh
  • 39,603