As per the title, I'm having some trouble to solve the recurrence equation
Edited
$$ T(N) = 2T \left(\left\lceil \frac{N+1}{2} \right\rceil\right) + 2T \left(\left\lfloor \frac{N+1}{2} \right\rfloor\right)$$
which is true for $N > 4$. I have two base cases, $T(3) = 6$ and $T(4) = 18$, but I'm stuck on how to proceed.
Best Answer
For the simplicity put $T(n)=6S(n)$ for each $n$. Then the sequence $S$ satisfies the same recurrence relation. A computed graph of the function $S$ suggests that it is piecewise linear with bends at $n=2^k+1$ and $2^k+2^{k-1}+1$. Indeed, by induction we can show that $S(2^k+1)=4^{k-1}$ and $S(2^k+2^{k-1}+1)=3\cdot 4^{k-1}$ for each $k\ge 1$. Also by induction we can show that between these points $S$ is linear, that is $$S(2^k+\lambda 2^{k-1}+1)=(1+2\lambda)4^{k-1}$$ and $$S(2^k+2^{k-1}+\lambda 2^{k-1}+1)=(3+\lambda)4^{k-1}$$ for each integer $2^{k-1}\lambda$ between $0$ and $2^{k-1}$. The found form of the function $S$ easily implies bounds $\frac {1}4\le\tfrac{S(n)}{ (n-1)^2}\le \frac 13$ (and $\tfrac 32(n−1)^2\le T(n)\le 2(n−1)^2$), for each $n\ge 3$.