I have been reading CLRS and came across a few examples of the Master theorem. I could not follow the reason that epsilon was chosen as 0.8 in the example from page 96 . Can I simply use the condition n^log(b) of a to determine the maximum value of epsilon? For example for case 3 where π(π)=Ξ©(πlogππ+π) for some constant π>0. T(n) =12T(n/2)+n^2. here the answer is n^ 3.58 so I am assuming it is n^3 and therefore Case 3 which means π(π)=Ξ©(πlogππ+π) : How do i choose a value for epsilon that will be the maximum allowed to make .My effort 3.58+π <1 seems nonsense. Which π is correct to this case, or does the Master theorem not apply. Can this method be also be applied to the other cases. case 1 has an epsilon, but case 2 does not. when epsilon is an integer it is staright forward, but not so obvious( to me ) when it is a decimal. help would be apprecaited
-
1$\begingroup$ Please edit the question to make it self-contained, so we can understand the relevant context and can understand what you're asking even if we don't have a copy of page 96 from CLRS in front of us. I am not sure what you mean by "maximum value of epsilon". $\endgroup$– D.W. ♦Mar 18, 2021 at 4:38
1 Answer
$\epsilon$ is simply a value bigger than $0$, there is no maximum possible value for it. If you can find any $\epsilon>0$ which makes either of the cases 1 or 3 of the master theorem true, then you have found the complexity for the algorithm (though additional checks might be needed for case 3 but it's not related to the question).
Considering the example you've provided in the question, $T(n)=12T(\frac{n}{2})+n^2$, we have $a=12, b=2,f(n)=n^2$. Checking the first case of the master theorem, we have $$f(n)=n^2\in \mathcal{O}(n^{log_{2}12-\epsilon})$$ which is true for let's say $\epsilon=\frac{1}{2}$ (since $n^2 < n^{log_211.5}$).
You can choose many other $\epsilon$'s that still satisfy the condition, but all you need to do is find one and you're good to go.
