# Finding lambda of Master Theorem

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?

-

## migrated from cstheory.stackexchange.comJun 1 '12 at 21:32

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

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

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