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.