Understanding the lambda as it applies to the Master Theorem

Question

Suppose i have a case like T(n)=2T(n/4)+1. f(n)=1 a=2 and b=4. Thus n^(1/2)>1. That should be case 1. However there is also a lambda in case 1, so that f(n)=O(n^((1/2)-lambda)) for some lambda >0. In this case lambda would be 1/2?

Answer 1

Yes, that's correct. Note that, in this case, we have that a = 2 and b = 4. The function f(n) in this case is 1, and we do have that 1 = Θ(n^{1/2 - ε}) for some ε > 0, where in this case ε = 1/2. Consequently, by the Master Theorem, you would get that T(n) = Θ(n^1/2).

The point of this ε is that if the amount of work done per level is sufficiently small (below log_b a), then the work is dominating primarily by the splitting rather than the work per level. The fact that you can subtract ε > 0 from the exponent indicates that the work per level must grow strictly asymptotically slower than the splitting rate, and must do so by some polynomial amount.

Hope this helps!