Solving recurrence equations with 2 base cases

285 Views Asked by At

I'm a little confused regarding solving recurrence equations with 2 base cases, so for T(n) =

\begin{cases} 1, & \text{if 0 < $n$ ≤ 2 } \\ T(n - 2) + 3, & \text{if $n$ > 2} \end{cases}

Using substitution I have T(n) = T(n - 2i) + 3i, and I'm stuck on what to do next, as there are 2 base cases T(2) and T(1).

1

There are 1 best solutions below

2
On

The recursion trees arising from the two base cases are completely independent of each other. Thus we may write for odd $n$ $$T(n)=\frac{3(n+1)}2-2$$ and for even $n$ $$T(n)=\frac{3n}2-2$$ which can be combined as $$T(n)=3\left\lceil\frac n2\right\rceil-2$$