Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
