How to find the recurrence relation using domain range substitution method for the below: $$ T(n) = 2T\left(\frac{n}{2} +1\right) + n -2 $$
I am unable to get a pattern with this relation as it is really confusing. I am guessing the below for $T(n/2 + 1)$: $$ T\left(\frac{n}{2} +1\right) = 2T\left(\frac{n+2}{4}+1\right)+ \frac{n+2}{2} - 2 $$
When I substitute this for $T(n)$ it becomes a mess.
Can someone guide me in this please.
Perhaps you can spot the pattern here: \begin{align} T(n) &= 2T\left(\frac{n+2}{2}\right) + n-2 \\ &= 4T\left(\frac{n+6}{4}\right) + 2n-4 \\ &= 8T\left(\frac{n+14}{8}\right) + 3n-6 \\ &= 16T\left(\frac{n+30}{16}\right) + 4n-8 \end{align} More generally, we have $$ T(n) = 2^k T\left(\frac{n-2}{2^k} + 2\right) + k(n-2). $$ This implies that $$ T(2^k+2) = 2^k T(3) + k2^k. $$
Hint.
Making $S(n) = T(n+a)$ we have
$$ S(n) = 2T\left(\frac{n+a}{2}+1\right)+n+a-2 $$
but
$$ T\left(\frac{n+a}{2}+1\right) = S\left(\frac{n+a}{2}+1-a\right) = S\left(\frac n2-\frac a2+1\right) $$
now choosing $a=2$ we follow with
$$ S(n)=2S\left(\frac n2\right)+n $$
etc.
