# Master method and choosing $\epsilon$

I am reading CLRS3, currently Chapter 4 and Section 4.5, "The master method for solving recurrences."

I understood what is the $\epsilon$ , but I can't understand why they choose $\epsilon \thickapprox 0.2$ here :

$$T(n) = 3T\left(\frac{n}{4}\right) + n\lg n$$ we have $a=3$, $b=4$, $f(n) = n\lg n$, and $n^{\log_b a}=n^{\log_4 3}=O(n^{0.793})$. Since $f(n) = \Omega(n^{\log_4 3+\epsilon})$, where $\epsilon \approx 0.2$, case 3 applies if we can show that the regularity condition holds for $f(n)$. [...] (See picture for a copy of the text.)

Can you help me ?

For Case 3 to apply, you need $f(n) = \Omega( n^{\log_b a+\epsilon} )$ for some constant $\epsilon>0$.
In this problem $a=3$, $b=4$ and $f(n) = n\log n$, so that you need to exhibit a value of $\epsilon>0$ such that $n\log n = \Omega(n^{\log_4 3+\epsilon})$; which amounts to saying $\underbrace{\log_4 3}_{\simeq 0.792}+\epsilon\leq 1$.
Here, they chose $\epsilon \simeq 0.2$ because this works. Absolutely any value of $\epsilon$ such that $$\log_4 3 < \log_4 3+\epsilon \leq 1$$ would have done the job as well.
• The problem is that the $\epsilon$ value should be nearly 0.2 because that's how order of is defined as. nlogn is considered here. Please read the book available online to get it's context. Commented Feb 9, 2016 at 3:04
• No. I reiterate, any value of $\epsilon$ as stated above would work... there is nothing special about the specific value $0.2$, read the statement of the theorem in the book (or point to an actual excerpt of it that says so). Furthermore, your comment on the tight "order of convergence" of $n\log n$ does not make sense: no matter the value of $\epsilon$, there is no possible choice that makes $n\log n = \Theta(n^{\log_5 4 + \epsilon})$. The only thing that matters is the $\Omega$ criterion, as stated both in the theorem and in its application; for which e.g. $\epsilon=0.001$ would also work. Commented Feb 9, 2016 at 3:57
• @Clement C : thanks very much. I got it . do we can't choose $\epsilon$ > 0.2 because of $n^{1+x} > n log n$ where $x \in R^{+}$ ? Commented Feb 9, 2016 at 7:39