Need help with recurrence relation and postcondition of a function
Without having checked if $T(n)$ is correct, you can find the closed form by:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lceil\dfrac{n}{2}\rceil - 1) + n*c_1 + c$$
If n is odd, you can rewrite $T(n)$ as:
$$T(n) = T(\lfloor\dfrac{n}{2}\rfloor) + T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c = $$
$$T(n) = 2T(\lfloor\dfrac{n}{2}\rfloor) + n*c_1 + c $$
If you substitute $T(\lfloor\dfrac{n}{2}\rfloor)$ you get
$$T(n) = 2( 2T(\lfloor\dfrac{n}{4}\rfloor) + \dfrac{n}{2}*c_1 + c  ) + n*c_1 + c =$$
$$T(n) = 4T(\lfloor\dfrac{n}{4}\rfloor) + 2n*c_1 + 3c $$
If you substitute $T(\lfloor\dfrac{n}{4}\rfloor)$ you get
$$ T(n) = 4 (2T(\lfloor\dfrac{n}{8}\rfloor) + \dfrac{n}{4}*c_1 + c) + 2n*c_1 + 3c = $$
$$ T(n) = 8T(\lfloor\dfrac{n}{8}\rfloor) + 3n*c_1 + 7c$$
Now you can observe the pattern and see that after substituting $\dfrac{n}{2^{k-1}}$
$$ T(n) = 2^kT(\lfloor\dfrac{n}{2^k}\rfloor) + k*n*c_1 + (2^0 + 2^1 +...+ 2^k)c$$
Let $n = 2^k$
$$ T(n) = nT(1) + n*log_2n*c_1 + (2^0 + 2^1 +...+ n)c = $$
$$ T(n) = n + n*log_2n*c_1 + (2^n - 1)c = $$
$$ T(n) = n + n*log_2n*c_1 + 2^n*c - c = $$
So you have $O(2^n)$
Now if n is even, you have
$$T(n) = T(\dfrac{n}{2}) + T(\dfrac{n}{2} - 1) + n*c_1 + c $$
And you follow the same method as before (i.e., start by substituting n/2 and find the pattern after a few iterations).