# Find time complexity of $T(n)=3T(n-2)+O(n)$

I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$

I wonder if the ans is $$O(3^{\frac{n}{2}})$$ or $$O(3^{\frac{n}{2}} n)$$, can someone give a help to determine the ans and give a proof about it.

• Note that big-O stays correct if the right side is unnecessarily large. 3^(n/2) * n is unnecessarily large. Oct 24, 2023 at 13:35

That said, assuming $$T(1)=O(1)$$ and $$T(2)=O(1)$$, both $$T(n)=O(3^{n/2})$$ and $$T(n)=O(3^{n/2} n)$$ are true. Indeed: $$T(n) = 3T(n-2)+O(n) =3^i T(n-2i) + \sum_{j=0}^{i-1} 3^j O(n-2j) \quad \text{for }i choosing $$i=\lfloor n/2 \rfloor - 1$$: \begin{align} T(n) &= 3^{\lfloor n/2 \rfloor - 1} \cdot O(1) + \sum_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j O(n-2j) = O\left( \sum_{j=0}^{\lfloor n/2 \rfloor - 2} 3^j (n-2j) \right) \\ &= O\left(3^{n/2} \sum_{j=0}^{\infty} \frac{1}{2^i} \right) = O(3^{n/2}). \end{align}
Where we used the fact that each term of the summation increases by at least a factor of $$2$$ compared to the previous one. Indeed: $$\frac{3^{j+1} (n-2j-2)}{3^j (n-2j)} = 3\left(1-\frac{2}{n-2j}\right) \ge 3\left(1-\frac{2}{n- 2(\lfloor n/2 \rfloor - 3)}\right) \ge 2.$$
The above shows that $$T(n) = O(3^{n/2})$$, which also implies $$T(n)=O(3^{n/2} n)$$.