How to solve the recurrence relation $T(n) = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2$ I'm trying to solve a recurrence relation for the exact function (I need the exact number of comparisons for some algorithm). This is what i need to solve:
$$\begin{aligned}
T(1) &= 0 \\
T(2) &= 1 \\
T(n) & = T(\lceil n/2\rceil) + T(\lfloor n/2\rfloor) + 2 \qquad(\text{for each $n\ge2$})
\end{aligned}$$
Without the ceiling and floor I know that the solution is $T(n) = 3n/2 -2$ if $n$ is the power of 2, but how can I solve it with them? (and for every $n$, not just $n$ that is the power of 2).
Thanks a lot.

We suppose that $T(n)=O(n)$
So, $\exists c,b>0 \text{ and } n_0 \geq 1 \text{ such that } \forall n \geq n_0:$
$$T(n) \leq cn-b$$
Suppose that the hypothesis stands also for $\lfloor \frac{n}{2} \rfloor$ and $\lceil \frac{n}{2} \rceil$:
$$T(\lfloor \frac{n}{2} \rfloor) \leq c\lfloor \frac{n}{2} \rfloor-b \\ T(\lfloor \frac{n}{2} \rfloor) \leq c\lceil \frac{n}{2} \rceil-b $$
Then:
$$T(n) \leq c\lceil \frac{n}{2} \rceil-b+c\lfloor \frac{n}{2} \rfloor-b+2=c(\lceil \frac{n}{2}+\lfloor \frac{n}{2} \rfloor)-2b+2 \\ =cn-b-(b-2) \leq cn-b \text{ if } b \geq 2 $$
Therefore, $T(n)=O(n)$.
