Finding solution of recurrence relations $T(n) = 2T(n/3)+n$

958 Views Asked by At

Evaluate:

$$T(n)=2T(n/3)+n$$

$$T(n/3)=2T(n/9)+n/3$$

$$T(n/9)=2T(n/27)+n/9$$

Substitute the following result:

$$T(n)=2(2(2T(n/27)+n/9)+n/3)+n$$

$$T(k)=2^k T(n/3^k)+n/3^{k-1}+n/3^{k-2}+....+n/3^0$$

$$T(k)=2^k T(n/3^k)+\frac{(1-1/3^k)}{(1-1/3)}n$$

Generalization: $$T(n/3^k=1)=1\text{, (Since T(1) = 1)}$$ $$T(n=3^k)=1$$ $$T(k=\log_3 n)=1$$
Thus: $$T(n)=2^{\log_3 n}T(n/3^{\log_3 n})+\frac{(1-1/3^{\log_3 n})}{(1-1/3)}n$$

$$T(n)=2^{\log_3 n}+3/2(n-1)$$

But when I tested the N input to the solution above, the result does not match with T(n) = 2T(n/3) + n. For example I input 27 to the following solution:

(NOTE: $T(3)=2T(1)+3=5$
$T(9)=2T(3)+9=19$
$T(27)=2T(9)+27=65$) $$T(27)=2^{\log_3 27}+3/2(27-1)=47$$

So I conclude that I might missed something with my derivation. But which part?

1

There are 1 best solutions below

4
On BEST ANSWER

In going from your line of

$$T\left(n\right)=2\left(2\left(2T\left(n/27\right)+n/9\right)+n/3\right)+n \tag{1}\label{eq1}$$

to the generalization of your next line, you forgot that the $2$ factors go across the various terms. As such, each term after the first of your next line should have a factor of $2$ to a decreasing power. For example, the result of expanding \eqref{eq1} becomes

$$T\left(n\right) = 2^3T\left(n/27\right) + 2^2n/9 + 2^1n/3 + 2^0n \tag{2}\label{eq2}$$

This, of course, will significantly affect the rest of your calculations.