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 have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is:

$$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$

Can i use the master theorem in that relation? If so, can i say that $T(n)=\Theta(\sqrt n)$?

Thanks

share|improve this question

2 Answers 2

up vote 1 down vote accepted

Note that you have $a=3$, $b=5$ and $f(n)=\sqrt n$ with respect to this description. Now, we have $\log_b(a)=\log_5(3)>0.6>0.5$. Thus, $f\in\Theta(n^c)$ for $c<\log_b(a)$ and we must apply case 1 of the master theorem, namely $$T \in \Theta(n^{\log_b(a)}) = \Theta(n^{\log_5(3)})$$ That is not quite the same, because $\log_5(3)\ne \frac 12$.

share|improve this answer
    
Thank you, that helped! –  bigO Mar 7 '13 at 11:21

This recurrence has an explicit solution when $T(0) = 0$ the same way as was done here.

Let $$n = \sum_{k=0}^{\lfloor \log_5 n \rfloor} d_k 5^k$$ be the base $5$ digit representation of $n.$ We assume that $T(0) = 0$ and that $$ T(n) = T(3 n/5) + \lfloor \sqrt n \rfloor.$$

It is not difficult to see that we have the following exact formula for all $n:$ $$ T(n) = \sum_{j=0}^{\lfloor \log_5 n \rfloor} 3^j \Bigg\lfloor\sqrt{\sum_{k=j}^{\lfloor \log_5 n \rfloor} d_k 5^{k-j}}\Bigg\rfloor.$$ Now to get an upper bound on this consider the case where all digits are equal to four. $$ T(n) \le \sum_{j=0}^{\lfloor \log_5 n \rfloor} 3^j \Big\lfloor\sqrt{5^{\lfloor \log_5 n \rfloor -j +1}-1} \Big\rfloor < \sum_{j=0}^{\lfloor \log_5 n \rfloor} 3^j \sqrt{5}^{\lfloor \log_5 n \rfloor -j +1} = \sqrt{5}^{\lfloor \log_5 n \rfloor +1} \sum_{j=0}^{\lfloor \log_5 n \rfloor} \left(\frac{3}{\sqrt 5}\right)^j \\ = \sqrt{5}^{\lfloor \log_5 n \rfloor +1} \frac{\left(\frac{3}{\sqrt 5}\right)^{\lfloor \log_5 n \rfloor +1}-1}{\frac{3}{\sqrt 5}-1} = \frac{3^{\lfloor \log_5 n \rfloor +1}-\sqrt{5}^{\lfloor \log_5 n \rfloor +1}}{\frac{3}{\sqrt 5}-1}.$$

For a lower bound, suppose that the leading digit is one and the rest are zero, giving $$ T(n) \ge \sum_{j=0}^{\lfloor \log_5 n \rfloor} 3^j \lfloor\sqrt{5^{\lfloor \log_5 n \rfloor-j}}\rfloor > \sum_{j=0}^{\lfloor \log_5 n \rfloor} 3^j \left(\sqrt{5^{\lfloor \log_5 n \rfloor-j}} - 1\right) \\ = \sqrt{5}^{\lfloor \log_5 n \rfloor} \sum_{j=0}^{\lfloor \log_5 n \rfloor} \left(\frac{3}{\sqrt 5}\right)^j - \frac{1}{2} \left( 3^{\lfloor \log_5 n \rfloor+1} - 1\right) \\= \sqrt{5}^{\lfloor \log_5 n \rfloor} \frac{\left(\frac{3}{\sqrt 5}\right)^{\lfloor \log_5 n \rfloor+1}-1}{\frac{3}{\sqrt 5}-1} - \frac{1}{2} \left( 3^{\lfloor \log_5 n \rfloor+1} - 1\right)\\= \frac{1}{5} \frac{3^{\lfloor \log_5 n \rfloor+1}-\sqrt{5}^{\lfloor \log_5 n \rfloor +1}} {\frac{3}{\sqrt 5}-1} - \frac{1}{2} \left( 3^{\lfloor \log_5 n \rfloor+1} - 1\right) $$ Taking the leading terms of the two bounds together we have shown that $$ T(n) \in \Theta\left(3^{\lfloor \log_5 n \rfloor}\right) = \Theta\left(3^{\log_5 n}\right) = \Theta\left(5^{\log_5 3 \log_5 n}\right) = \Theta\left(n^{\log_5 3}\right).$$ Here we have used the fact that $1/5\, \left( 3/5\,\sqrt {5}-1 \right) ^{-1}-1/2>0.$

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.