# Solving the recurrence relation $T(n)=2T(n/4)+\sqrt{n}$

I've solved $T(n)=2T(n/4)+\sqrt{n}$ to equal $2^{\log_{4}n}(\log_{4}n+1)$, but I'm not sure how to solve it directly.

I have:

$2(2T(\frac{n}{16})+\sqrt{\frac{n}{4}})+\sqrt{n} = 4T(\frac{n}{16})+2\sqrt{n}$

$2(4T(\frac{n}{64})+2\sqrt{\frac{n}{16}})+\sqrt{n} = 8T(\frac{n}{64})+2\sqrt{n}$

$2(8T(\frac{n}{256})+2\sqrt{\frac{n}{64}})+\sqrt{n}=16T(\frac{n}{256})+\frac{5}{4}\sqrt{n}$

I'm not seeing a pattern here and I'm not sure I'm modifying $n$ as necessary. What's the problem?

-
Hey you can use the master theorem and it's easier!!! –  user135647 Mar 15 '14 at 17:33

Let's turn the equation $T(n) = 2 T(n/4) + \sqrt{n}$ into a recurrence equation. To this end, let $f(m) = T(4^m p)$ for some $p>0$. Then $$f(m) = 2 f(m-1) + \sqrt{p} 2^m$$ which can be systematically solved. First rewrite it as $$2^{-m} f(m) - 2^{-(m-1)} f(m-1) = \sqrt{p}$$ Then sum equations from $m=1$ to some upper bound $k$: $$\sum_{m=1}^k \left(2^{-m} f(m) - 2^{-(m-1)} f(m-1) \right) = \sum_{k=1}^m \sqrt{p}$$ The sum on the left-hand-side telescopes: $$\begin{eqnarray} \sum_{m=1}^k \left(2^{-m} f(m) - 2^{-(m-1)} f(m-1) \right) &=& \left(2^{-m} f(m) - \color\green{2^{-(m-1)} f(m-1)}\right) + \\ &\phantom{=}& \left(\color\green{2^{-(m-1)} f(m-1)} - 2^{-(m-2)} f(m-2)\right) + \\ &\phantom{=}& \vdots \\ &\phantom{=}& \left( 2^{-2} f(2) - \color\green{2^{-1} f(1)} \right) +\\ &\phantom{=}& \left( \color\green{2^{-1} f(1)} - 2^{-0} f(0) \right) \\ &=& 2^{-m} f(m) - f(0) \end{eqnarray}$$ Hence we arrive at the solution $$f(m) = 2^m \left( m \sqrt{p} + f(0) \right)$$ since $m = \log_4 \left(\frac{n}{p}\right)$ we get: $$T(n) = \sqrt{\frac{n}{p}} \left( \sqrt{p} \cdot \log_4 \frac{n}{p} + f(0)\right) = \sqrt{n} \log_4(n) + d \sqrt{n}$$ where $d$ is a free constant to be determined by the initial condition.

-
I'm afraid I don't understand the steps involved here, but I really appreciate the effort and have upvoted the answer. Could you please add a beginner-level version using the approach in the OP? –  mirai Oct 20 '12 at 3:09
@miray I have filled in the solution in more details. Please let me know if it still remains unclear. –  Sasha Oct 20 '12 at 3:20
Thanks, I really appreciate it. –  mirai Oct 20 '12 at 16:30

There is another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 2 T(\lfloor n/4 \rfloor) + \lfloor \sqrt{n} \rfloor.$$

Furthermore let the base four representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_4 n \rfloor} d_k 4^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j\Bigg\lfloor \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} d_k 4^{k-j}} \Bigg\rfloor.$$

Now to get an upper bound consider a string of digits with value three to obtain

$$T(n) \le \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{\sum_{k=j}^{\lfloor \log_4 n \rfloor} 3\times 4^{k-j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j} -1} \\ < \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor +1 - j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} \sqrt{4^{\lfloor \log_4 n \rfloor +1}} \\ = (\lfloor \log_4 n \rfloor + 1) \times 2^{\lfloor \log_4 n \rfloor +1}.$$

This bound is actually attained and cannot be improved upon, just like the lower bound, which occurs with a one digit followed by zeroes to give $$T(n) \ge \sum_{j=0}^{\lfloor \log_4 n \rfloor} 2^j \sqrt{4^{\lfloor \log_4 n \rfloor-j}} = \sum_{j=0}^{\lfloor \log_4 n \rfloor} \sqrt{4^{\lfloor \log_4 n \rfloor}} \\ = (\lfloor \log_4 n \rfloor + 1) \times 2^{\lfloor \log_4 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\lfloor \log_4 n \rfloor \times 2^{\lfloor \log_4 n \rfloor} \in \Theta\left(\log_4 n \times 4^{1/2 \log_4 n}\right) = \Theta\left(\log n \times \sqrt{n}\right).$$

Observe that there is a lower order term $$2^{\lfloor \log_4 n \rfloor} \in \Theta\left(4^{1/2 \log_4 n}\right) = \Theta\left(\sqrt{n}\right).$$

The above is in agreement with what the Master theorem would produce.

Addendum Nov 3 2014. The lower bound is missing a lower order term, which is $-(2^{\lfloor \log_4 n \rfloor+1}-1)$ the same as was done at this MSE link.

Here is another computation in the same spirit: MSE link.

-