JEST 2019

Question

Solve the recurrence relation given as: T(n)=2T(n-2)+n; where T(2)=2 and T(1)=0

What is the solution?

Answer 1

This can be solved using Master Theorem for Subtract and Conquer Recurrences which states that 

T(n)= {c if $n≤1$ ; $aT(n-b)+f(n)$ if $n>1$}

for some constants $c,a>0,b>0 , k≥0$ and function f(n). If f(n) is in O($n^k$), then 

T(n) = O($n^k a^{n/b}$) if a>1 

Accordingly ans should be O($n2^{n/2}$)