Recurence Problem. - Solve either by substitution or Expansion

Question

Function T(n) is defined by the following recurrence relation:

$$ T(n)=2T(\lfloor\sqrt{ n}\rfloor)+\log(n) $$

$$ T(0)=1 $$

How would I Solve by substitution and/or Expansion?

Note: Correct answer: $\Theta(\log(n) \times \log (\log(n))) $

Answer 1

Here is how to get an upper bound, you can use similar reasoning to get the lower bound. First establish that $T(1)=0$ by algebraic manipulation, then note that $T(n)$ is monotonically increasing for $n\ge 1$. Thus we can get that for all $n$ greater then or equal to one we have: $T(\lfloor{n}\rfloor)\leq T(n)$ which gives us:

$$T(\lfloor{n}\rfloor)\leq 2T(\lfloor{n^{1/2}}\rfloor)+\ln(n)$$ $$\text{Now subtracting }2T(\lfloor{n^{1/2}}\rfloor) \text{ from both sides of the inequality:}$$ $$T(\lfloor{n}\rfloor)-2T(\lfloor{n^{1/2}}\rfloor)\leq\ln(n)$$ $$\text{ Multiplying both sides by }2^{k-1} \text{ gives: }$$ $$2^{k-1}T(\lfloor{n}\rfloor)-2^kT(\lfloor{n^{1/2}}\rfloor)=2^{k-1}\ln(n)$$ $$\text{ Setting }n=m^{1/2^{k-1}} \text{ gives: }$$ $$2^{k-1}T(\lfloor{m^{1/2^{k-1}}}\rfloor)-2^{k}T(\lfloor{m^{1/2^{k}}}\rfloor)=\ln(m)$$ $$\text{Summing from } k=1 \text{ to an integer } k=L \text{ gives us a telescoping series which results in:}$$ $$T(\lfloor{m}\rfloor)-2T(\lfloor{m^{1/2}}\rfloor)+2T(\lfloor{m^{1/2}}\rfloor)-4T(\lfloor{m^{1/4}}\rfloor)+...=L\ln(m)$$ $$\text{ Then canceling like terms gives:}$$ $$T(\lfloor{m}\rfloor)-2^{L}T(\lfloor{m^{1/2^L}}\rfloor)\leq L\ln(m)$$ $$\text{Now set } L=\lceil{\log_2(\log_2(m))}\rceil+1 \text{ and note that: } m^{1/2^{L}}\leq m^{1/2^{\log_2(\log_2(m))+1}}<m^{1/2^{\log_2(\log_2(m)}}=2$$ $$\text{ Implying } \lfloor{m^{1/2^{L}}}\rfloor=1 \text{ which gives us that:}$$ $$T(\lfloor{m}\rfloor)-2^{L}T(\lfloor{m^{1/2^L}}\rfloor)\leq (\lceil{\log_2(\log_2(m))}\rceil+1)\ln(m)$$ $$\text{ And so we have:}$$ $$T(\lfloor{m}\rfloor)\leq (\lceil{\log_2(\log_2(m))}\rceil+1)\ln(m)$$ $$\text{Now letting } m=r+1 \text{ gives us that: }$$ $$T(r)\leq T(\lfloor{r}\rfloor+1)\leq (\lceil{\log_2(\log_2(r+1))}\rceil+1)\ln(r+1)$$ $$\text{ Thus we get:}$$ $$T(r)=O(\log(r)\times \log(\log(r))$$