tight asymptotic bound for $T(n) = 2T(n/4 - 100) + \sqrt n $ I just learned solving recurrence relation using substituion method.
I am currently stucked in this question.
I need to find a tight asymptotic bound for $$ T(n) = 2T(\frac{n}{4} - 100)+ \sqrt n$$
where $ T(n) = c$ , a positive integer and for $ n \le 2$
I have tried to use the substituion method in which I  guess $$ T(n) = \theta(n \text{lg}n)$$ using the reference from basic algorithm efficiency class, now I want to show that both the upper bound and lower bound of $T(n)$ to prove that my guessing is correct.
to prove upper bound case, by substituion I will do by induction hypothesis and definition of big-O to prove that $T(n) \le c \cdot n \text{lg} n$
$$ T(n) = 2T(\frac{n}{4} - 100)+ \sqrt n$$
$$\le 2c(\frac{n}{4} - 100)\text{lg}(\frac{n}{4}-100) + \sqrt n$$
$$=(\frac{cn}{2} - 200c)\text{lg}(\frac{n}{4}-100) + \sqrt n$$
$$<(\frac{cn}{2} - 200c)\text{lg}(\frac{n}{4}) + \sqrt n  $$
$$=(\frac{cn}{2} - 200c)(\text{lg}n - \text{lg}4) + \sqrt n  $$
$$=(\frac{cn}{2} - 200c)(\text{lg}n - 2) + \sqrt n  $$
$$\le(\frac{cn}{2} - 200c)(\text{lg}n) + \sqrt n  $$
$$=\frac{cn\text{lg}n}{2} - 200c\text{lg}n + \sqrt n  $$
Then I am really stucked in here on how to prove that the above is $\le cn\text{lg}n$
Any help will be appreciated!
 A: You should be able to get something out of $V(p)=U(4^p)=U(3n+400)=2\dfrac{T(n)}{\sqrt{3n+400}}$

*

*the $3n+400$ transform takes care of $\frac n4-100$ offset

*the $4^p$ transform takes care of the $LHS(n)=RHS(\frac n4)$

*the $U=\frac{2T}{\sqrt{n}}$ takes care of the equation $T(.)=2T(.)+\sqrt{n}$ (master theorem)


$\begin{align}U(3n+400)&=\dfrac{2T(n)}{\sqrt{3n+400}}\\\\
&=\dfrac{2\bigg(2T(\frac n4-100)+\sqrt{n}\bigg)}{\sqrt{3n+400}}\\\\
&=\dfrac{2\bigg(\sqrt{3(\frac n4-100)+400}\times U(3(\frac n4-100)+400)+\sqrt{n}\bigg)}{\sqrt{3n+400}}\\\\
&=\dfrac{2\sqrt{\frac 14(3n+400)}\times U(\frac 14(3n+400)+2\sqrt{n}}{\sqrt{3n+400}}\\\\
&=U(\frac 14(3n+400))+2\sqrt{\frac n{3n+400}}
\end{align}$
Now lets do the $4^p$ substitution : $U(4^p)=U(4^{p-1})+2\sqrt{\frac{4^p-400}{3\times 4^p}}$
This gives the telescopic : $V(p)-V(p-1)=\frac 2{\sqrt{3}}\sqrt{1-\dfrac{400}{4^p}}$
$V(p)=V(0)+\frac{2}{\sqrt{3}}\sum\limits_{k=1}^p\sqrt{1-\dfrac{400}{4^k}}$
In first approximation that makes $V(p)\sim \dfrac{2p}{\sqrt{3}}\implies T(n)\sim \dfrac{p\ \sqrt{3n+400}}{\sqrt{3}}$
Going back to $n$ with $4^p=3n+400$ this gives $p=\frac 12\log_2(3n+400)\sim\frac 12\log_2(n)$

Thus $T(n)\sim \frac 12\sqrt{n}\log_2(n)$

Now if you want a better approximation you can develop $V(p)$ with a higher order Taylor expansion (not easy since $\sum o(4^{-\alpha k})$ still has a constant part in it, for all $\alpha$), but you get the idea. Maybe just going for $V(p)=\frac{2p}{\sqrt{3}}+C+o(1)$ with some unknown constant $C$ is sufficient.
