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

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?

• "\$\epsilon = 1\$" gives "$\epsilon = 1$". You can lose the quote marks if you don't want them surrounding the math. The dollar signs are there so that this web site knows whatever's between there is a mathematical expression, and not just plain text. It will then typeset it as such. Not so important for things this simple, but any nightmarishly long expression (especially with exponents etc.) get much worse without them. Oct 21, 2013 at 13:30
• For some basic information about writing math at this site see e.g. here, here, here and here. Oct 22, 2013 at 3:21

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