Is it possible to calculate the closed form solution for the following recurrence relation?
$$ T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{2} + 1\right) + \frac{n}{2} $$
I am trying to teach myself about this stuff, and I see that it is similar in form to
$$ T(n) = \alpha T\left(\frac{n}{b}\right) + f(n) $$
But the second term of $T\left(\frac{n}{2} + 1\right) $ is messing me up.
For $n=0$, this yields $T(0)=T(0)+T(1)$. For $n=2$, this yields $T(2)=T(1)+T(2)+1$. Thus $T(1)=0=T(1)+1$, which might be seen as a problem.