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})$.

Dark Mode

134 views

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?

If n = 0 then T(n) = 1

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

What is the generalized solution?

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