1
$\begingroup$

I have a recurrence relation: $$T(n) = 3T(\frac{n}{4}) + n\lg n$$

and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're choosing $\epsilon = 0.2$. For example:

$$n^{\log_b a}=n^{\log_4 3} \Rightarrow n\lg n = \Omega(n^{0.79+\epsilon})$$

Why would we choose $\epsilon = 0.2$, why couldn't we have chosen something like $\epsilon = 0.0001$, wouldn't this already be enough?

$\endgroup$
1
$\begingroup$

First, note that $\log_4 3 = 0.792...$. Now the key observation is that $n^{0.792..}$ grows asymptotically slower than $n \lg n$, i.e., $n^{0.792...} = O(n \lg n)$, or if you prefer, $n \lg n = \Omega(n^{0.792...})$. Why? Well, one way to see it is to notice that $n^{0.792...} = O(n)$ and $n = O(n \lg n)$: $n^{0.792...}$ grows asymptotically slower than $n$, because the exponent is smaller; and $n$ grows asymptotically slower than $n \lg n$.

What's up with the $\epsilon=0.2$? That's probably a clunky way of getting at the fact that $n^{0.792...}$ is smaller than $n^{1.000...}$. In particular, $0.792 + 0.2 < 1.0000$. Personally, I don't find it a particularly helpful explanation for why $n^{0.792...} = O(n)$, so I would suggest you ignore it. If you find it confusing, it's not just you, and it doesn't represent some shortcoming in your understanding; it just seems like a confusing way to explain it to me.

$\endgroup$
  • $\begingroup$ @ D.W. so I could use $\epsilon=0.00001$ if I wanted to? $\endgroup$ – Yos Apr 14 '17 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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