Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Hey you can use the master theorem and it's easier!!! –  richard clare Mar 15 at 17:33

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
    
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.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.