For the recurrence $T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ is in $\Theta(lg n)$
My attempt at a solution (mostly just wanting to verify its correct).
Lower Bound:
$T(n)=2*\lceil\frac{n+1}{2}\rceil+c$ (assuming that for small inputs), T(n)=c
Base case: $a*lg(n)\leq c$ take $n_{o}=2, a=c$
Inductive step: Assume that for all input sizes k smaller than n, they are lower bounded by $a*lg(n)$
$a*lg(n)\leq 2*(a*lg\frac{n+1}{2})+c$
$a*lg(n)\leq 2a*lg(n+1)-2a+c$
If a=c then this holds and c>=1 then:
$c*lg(n)<=2c*lg(n+1)-c$
Upper Bound:
$T(n)=c\leq a*lg(n)$ take no=2 and a=2c then this holds
$T(n)<=a*lg(n)$
$2a*lg(\frac{n+1}{2})+c\leq a*lg(n)$
$2a*lg(n+1)-1+c\leq a*lg(n)$
$2a*lg(n+1)-2a+c\leq a*lg(n)$ If a is 2c then:
$2c*lg(n+1)-3c\leq 2c*lg(n)$ note that lg(n+1)-lg(n) is less than 1 if n is sufficiently large and that c is at least 1.