algorithmcomplexity-theorymaster-theorem

What exactly does epsilon represent in master theorem?


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:

enter image description here

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!


Solution

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

    With c_crit = log_b(a):

    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.