1
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ $T(n) \neq \Theta(n \ln n)$, which can be verified by applying the Akra-Bazzi method. $\endgroup$
    – Maxim
    Commented Sep 25, 2020 at 17:36

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Hi, i was not able to understand your comment, can you please elaborate more on that? thank you. $\endgroup$
    – Sanny H
    Commented Sep 25, 2020 at 17:40
  • $\begingroup$ I was not fond of doing all the calculations in the first place, but here it is. As suggested in the comments you can as well apply directly the Akra-Bazzi theorem, my answer just shows you the reason why we get there with the theorem. Note that with simpler equations, we sometimes manage to get an exact closed form for $T(n)$, so the method worth learning. $\endgroup$
    – zwim
    Commented Sep 27, 2020 at 12:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .