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!
You don't need the epsilon to state the Master Theorem. Wikipedia gives another formulation:
With c_crit = log_b(a)
:
f(n) = O(n^c)
where c < c_crit
, then T(n) = Θ(n^c_crit)
;f(n) = Θ(n^c_crit log(n)^k)
for any k >= 0
, then T(n) = Θ(n^c_crit log(n)^(k+1))
;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.