$T(n) = 2T(n-2) + n$ Running Time

Question

Recurrence $T(n) = 2T(n-2) + n$

First call $n$

Second call $2(n-2)$

Third call: $2^2(n-2^2)$

per level: $2^in+4^i$ or $2^i(n-2^i)$

node formula with height h: $n-(2+(2*(h-1))$ gives for leaf condition $h=n/2$

so the Running Time over all levels should be

$$\sum_{i=0}^{n/2} 2^{i}(n-2^i) $$

splitted into two sums that is $$n*\sum_{i=0}^{n/2} 2^{i} $$ - $$\sum_{i=0}^{n/2} 4^{i} $$

So shouldn't that be $2*n*\sqrt(2)^n -2n - 4/3*2^n - 4/3$

and therefore $Theta(n*\sqrt(2)^n)$?

Answer 1

As

$$t_n - 2t_{n-2} = n,$$

it holds that

$$t_{n-2} - 2t_{n-4} = n-2.$$

If we subtract second equation from the first, we get

$$t_n - 3t_{n-2} +2t_{n-4} = 2.$$

Therefore,

$$t_{n-2} - 3t_{n-4} + 2t_{n-6} = 2.$$

By subtracting again, we get

$$t_n - 4t_{n-2} + 5t_{n-4} - t_{n-6} = 0.$$

Now, we get characteristic equation

$$x^6 - 4x^4 + 5x^2 - 2 = 0,$$

or, if we introduce $y = x^2$,

$$y^3 - 4y^2 + 5y - 2 = 0.$$

From the last equation we can conclude that roots are $y_{1,2} = 1$, and $y_3 = 2$. If we return to the original variable, that means that $x_{1,2} = 1$, $x_{3,4} = -1$, $x_5 = \sqrt{2}$ and $x_6 = -\sqrt{2}$, and the general solution for the recursion is

$$t_n = C_1\cdot 1^n + C_2\cdot n\cdot 1^n + C_3\cdot(-1)^n + C_4\cdot n\cdot (-1)^n + C_5\cdot(\sqrt{2})^n + C_6(-\sqrt{2})^n.$$

That gives the complexity

$$T(n) = \Theta\left((\sqrt{2})^n\right) = \Theta\left(2^\frac{n}2\right).$$

Answer 2

This is a linear recurrence relation, so you can solve the homogeneous equation:

$T(n)=2T(n-2)$ whose characteristic is $r^2-2=0$ thus $r=\pm\sqrt{2}$ and $$T_h(n)=(a+(-1)^nb)\sqrt{2}^n$$

Now find a particular solution with RHS of the form $T_p(n)=cn+d$

$\implies cn+d=2(c(n-2)+d)+n\implies (c+1)n+(-4c+d)=0$

Thus $T_p(n)=-n-4$ and we have

$$T(n)=\bigg(a+(-1)^nb\bigg)(\sqrt{2})^n-n-4$$