-1
$\begingroup$

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

$\endgroup$
1
  • 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.
    Commented Mar 18, 2021 at 4:38

1 Answer 1

0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Is there any "efficient" way of finding an epsilon value that works? $\endgroup$ Commented Feb 10 at 22:08

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.