**Problem Detail:**

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?

###### Asked By : Luc Peetersen

#### Answered By : Juho

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).$$

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2192

**3.2K people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback