# Master theorm and epsilon value

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

• 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".
– D.W.
Mar 18, 2021 at 4:38

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