I understand substitution method and recursion trees. I understand how to use master theorem but don't understand it's proof or intuitive explanation, specifically i don't understand where does the epsilon value come from in the theorem

The Master's Theorem states:

I am studying from CLRS 3rd edition, page 97. I want to know what does epsilon value represent, how do we come up with epsilon in the proof and Why do we need it. Would some other resource / book for this proof and extended master theorem proof!

CodePudding user response：

You don't need the epsilon to state the Master Theorem. Wikipedia gives another formulation:

With c_crit = log_b(a):

• if f(n) = O(n^c) where c < c_crit, then T(n) = Θ(n^c_crit);
• if f(n) = Θ(n^c_crit log(n)^k) for any k >= 0, then T(n) = Θ(n^c_crit log(n)^(k 1));
• if f(n) = Ω(n^c) where c > c_crit, and a*f(n/b) <= k*f(n) for some k < 1 and sufficiently large n, then T(n) = Θ(f(n)).

Essentially, the epsilon in your example is to make sure that log_b(a)-ε < log_b(a) and log_b(a) ε > log_b(a) (when ε > 0), just like c < c_crit and c > c_crit in this example from Wikipedia.