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$.
How to solve the recurrence relation $T(n) = 2T(\frac{2n}{3})$, where $T(0) = T(1) = 1$?
-
0@J.D. Same situation as in the above comment. Thanks for the suggestion! β 2012-02-01
4 Answers
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?
$\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.
-
1@MichaelLugo without initial conditions, azarel's answer is completely correct! β 2012-01-31
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.
-
0Itβs okay: I sometimes overlook them myself. β 2012-01-31
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.)