tight asymptotic bound for $T(n) = 2T(n/4 - 100) + \sqrt n $

Question

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!

Answer 1

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.