5
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ What you said is not true... You are reading in the context of the book. $\endgroup$ Commented Feb 9, 2016 at 0:39
  • $\begingroup$ @WinVineeth What do you mean? What did I say that is wrong — can you be specific? $\endgroup$
    – Clement C.
    Commented Feb 9, 2016 at 0:44
  • $\begingroup$ 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. $\endgroup$ Commented Feb 9, 2016 at 3:04
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Commented Feb 9, 2016 at 3:57
  • $\begingroup$ @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^{+}$ ? $\endgroup$
    – bluemmb
    Commented Feb 9, 2016 at 7:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .