Where is the value of the variable $\epsilon$ obtained in the following explanation my professor gave?

Question

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?

Answer 1

There is one function that is linear that solves it, $f(n)=-n/2$, but the general expression for $g(n)=f(n)+n/2$ is $g(n)=9g(n/3)$, so the obvious solution to that is $g(n)=An^2$. I don't know what he means by $\epsilon=1$.

Answer 2

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$.)