in Algorithms retagged by
134 views
0 votes
0 votes
T(n) = 3T(n-1) -4T(n-2) + 2T(n-3)

If n = 0 then T(n) = 1

 if n= 1 or 2 then T(n) = 0

What is the generalized solution?
in Algorithms retagged by
134 views

4 Comments

If we do this by recursion tree method,
Left subtree will go till $3^{n}$, middle subtree will go till $4^{n/2} = 2^{n}$ and right subtree will go till $2^{n/3}$.

Overall time = $O(3^{n})$.
1
1

it is asking for the generalized solution .

no doubt it is np complete.

1
1

$T_n = 3T_{n-1} \  – \ 4T_{n-2} + 2T_{n-3}$ with $T_0=1,T_1=T_2=0$ or,

$T_n - 3T_{n-1} \  + \ 4T_{n-2} - 2T_{n-3} = 0$ with $T_0=1,T_1=T_2=0$

This is a linear homogeneous recurrence of order 3. So, suppose, given recurrence has a solution $T_n = c\alpha^n; c \neq 0$ [Since, we are guessing the solution, later we can prove that our guessed solution is correct by using induction.]

Now, our guessed solution will satisfy the recurrence. So,

$c\alpha^n \  – \ 3c\alpha^{n-1} + 4c \alpha^{n-2} \  – \ 2c\alpha^{n-3} = 0$

$\alpha^3 – 3\alpha^2 + 4\alpha \  – \ 2 = 0$ (This is our characteristic polynomial and we need to find its roots.)

$\alpha^3 \  – \ \alpha^2 \  – \ 2\alpha^2  + 4\alpha \  – \  2 = 0$

 $\alpha^2(\alpha \ -\ 1) \ – \ 2(\alpha\ – \ 1)^2 = 0$

$(\alpha-1) (\alpha^2 \ – \ 2\alpha + 2) = 0$

Hence, $\alpha = 1, 1\pm i$

Therefore, Solution of the given recurrence is: $T_n = a_1\times 1^n + a_2 (1+i)^n +a_3 (1-i)^n $

So, $T_n = a_1 + a_2 (1+i)^n +a_3 (1-i)^n $ where $a_1,a_2,a_3$ are arbitrary constants.

Now, to find $a_1,a_2,a_3,$ you need to use $T_0=1,T_1=T_2=0$ and most important thing is here $a_1,a_2,a_3$ are not reals. These are complex numbers, so you need to assume like $a_1=x_1 + iy_1,a_2=x_2 + iy_2,a_3=x_3 + iy_3.$

You can try to find the reason why these are not reals by assuming it reals and what will be the values of $a_1,a_2,a_3.$

Try it. If you stuck, I will attach the further solution to find $a_1,a_2$ and $a_3.$

At the end you will get the same solution which @Abhrajyoti00 has mentioned above.  

 

1
1

Please log in or register to answer this question.