6 of 8
deleted 8 characters in body

# Meaning of polynomially larger or smaller in the context of the master method

I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $$n^{\log_ba}$$ being polynomially smaller or larger than $$f(n)$$.

What I mean is $$n^{\log_ba}$$ being polynomially larger or smaller than the function $$f(n)$$ for recurrence relations of the form: $$T(n) = aT(\dfrac nb) + f(n)$$.

Case 1 is the case in which $$n^{\log_ba}$$ is polynomially larger than $$f(n)$$.
Case 2 is the case in which $$n^{\log_ba}$$ is equal to $$f(n)$$.
Case 3 is the case in which $$n^{\log_ba}$$ is polynomially smaller than $$f(n)$$.

As my book defines it, for case 1 to apply $$n^{\log_ba-\epsilon}$$ for some $$\epsilon > 0$$ must be larger than $$f(n)$$. in other words, $$n^c > f(n)$$ where $$c< \log_ba$$.

Similarly, for case 3 to apply $$n^{\log_ba+\epsilon}$$ for some $$\epsilon > 0$$ must be smaller than $$f(n)$$ or in other words $$n^c < f(n)$$ where $$c > \log_ba$$.

Another way to think of subtracting $$\epsilon$$ is to think of $$\dfrac{n^{\log_ba}}{ n^e}$$ for some $$\epsilon > 0$$.

and another way to think of the adding of the $$\epsilon$$ is to think of $$n^{\log_ba}*n^\epsilon$$ for some $$\epsilon > 0$$.

In my class slides on the master method the first example uses the recurrence $$T(n) = 4T(\dfrac n2) + 1$$ and suggests the possibility that case 1 applies. $$n^{\log_ba}$$ would be $$n^2$$ and $$f(n)$$ would be 1.

The slide points out that $$f(n)$$ is NOT polynomially smaller than $$n^2$$.

I do not fully understand this because if you take $$0 > \epsilon > 1$$ such as $$1/2$$ for example.

You can then subtract this epsilon from $$n^2$$ and you'd have $$n^{1.5}$$ which would still be greater than $$f(n) = 1$$ for any $$n > 1$$.

So how is this not an example of being polynomially smaller?

Further, the slide which explains that $$f(n)$$ in this example is not polynomially smaller, indicates that $$T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$$ doesn't work

but why would they have attempted to divide $$n^2$$ by $$\log n$$ in the first place? I get the the division is equivalent to subtracting an $$\epsilon$$ from the exponent of $$n$$, but why $$\log n$$, what is the significance?