Master theorm and epsilon value

Question

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

Answer 1

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