My professor gave us this explanation from the textbook Introduction to Algorithms regarding the Master Method/Theorem:
As a first example, consider $$T(n)=9T(n/3)+n.$$ For this recurrence,
we have $a=9$, $b=3$, $f(n)n$, and thus we have that
$n^{log_b{a}}=n^{log_3{9}}=\Theta(n^2)$. Since
$f(n)=O(n^{log_3{9-\epsilon}})$, where $\epsilon=1$, we can apply case
1 of the master theorem and conclude that the possibility is
$T(n)=\Theta(n^2)$.
I'm very confused where the "$\epsilon$ = 1" comes from. Above in another explanation it says "for some constant $\epsilon$ > 0" but that obviously gives us the possibility of any number from $1$ to $\infty$. How is $1$ obtained?
Best Answer
As you say in your answer, you want to apply the master theorem with $a = 9$, $b = 3$, and $f(n) = n$. To do that, you also need some $\varepsilon$ such that $f(n) = O(n^{\log_b a} - \varepsilon)$, i.e. such that $n = O(n^{2 - \varepsilon})$ (since $\log_b a = 2$ in this case).
So the obvious power to use is $n^1$ — certainly you have $n = O(n^1)$. So you want $2-\epsilon = 1$, which gives $\varepsilon = 1$.
(You could just as well take $\varepsilon = 1/2$, or any other value in $(0,1]$. The two things you need to apply the theorem are just that $\varepsilon > 0$, and that $n = O(n^{2 - \varepsilon})$; the second of these is equivalent to $1 \leq 2 - \varepsilon$, and hence to $\varepsilon \leq 1$.)