Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$.

That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: $f(n)=O(n^{(1/2)-\lambda})$. Is this correct? And how can I find this lambda?

share|improve this question

migrated from cstheory.stackexchange.com Jun 1 '12 at 21:32

This question came from our site for theoretical computer scientists and researchers in related fields.

3  
Any $\lambda < 1/2$ will do in this case. –  Yuval Filmus Jun 1 '12 at 22:14

1 Answer 1

up vote 5 down vote accepted

As you correctly noted, the case 1 of the Master theorem applies here. In other words, the case 1 applies if $f(n) = O(n^{\log_b a - \lambda})$ for some constant $\lambda > 0$.

Indeed, we will have to see if we can find some $\lambda > 0$ so that in this case, $\log n = O(n^{\log_4 2 - \lambda}) = O(n^{1/2-\lambda})$. Easy, we can pick any $\lambda < 1/2$. Finally, be careful what the Master theorem now tells you: the solution to the recurrence

$$T(n) = \Theta(n^{\log_4 2}) = \Theta(n^{1/2}) = \Theta(\sqrt n).$$

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.