# 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?

*Edit: my professor's response:

As an example (assuming all numbers are positive to keep it sjmple), the idea is that for any numbers $$p$$ and $$q$$, if $$q > p$$, $$(n^p)*log(n) < n^q$$ asymptotically, no matter how close to $$p$$ the number $$q$$ is.

So $$n^p*log(n)$$ is not polynomially larger than $$n^p$$ because for any $$q > p$$, eventually it will be smaller then $$n^q$$

• "being polynomially smaller or larger than"? Can you edit the question to quote its definition? Can you also mention explicitly which case or which extension of case 2 of master theorem you are talking about each time? – Apass.Jack Mar 5 at 3:08
• @Apass.Jack thank you for attempting to help. I've made some edits to clarify as much as possible – Trixie the Cat Mar 5 at 3:44

It looks like there is some typo/inconsistency/misunderstanding somewhere in your class, the slides or your post. Hence, I will start from scratch, addressing the problems I can recognize.

Definition of polynomial differences. $$f(n)$$ is polynomially smaller than $$g(n)$$ if $$f(n) = O(g(n)/n^\epsilon)$$ for some $$\epsilon > 0$$. $$f(n)$$ is polynomially larger than $$g(n)$$ if $$f(n) = \Omega(g(n)n^\epsilon)$$ for some $$\epsilon > 0$$.

Here are some examples.

• $$f(n)=1$$ and $$g(n)=n^2$$. Then $$f(n)$$ is polynomially smaller than $$g(n)$$. This is what you believed and it is correct.
• $$f(n)=g(n)=n^2$$. Then $$f(n)$$ is not polynomially smaller nor polynomially larger than $$g(n)$$.
• $$f(n)=n^{1+\frac{1000}{\log n}}$$ and $$g(n)=n^2$$. Then $$f(n)$$ is polynomially smaller than $$g(n)$$.
• $$f(n)=\dfrac{n}{\log n}$$ and $$g(n)=n$$. Then $$f(n)$$ is not polynomially smaller nor polynomially larger than $$g(n)$$.

### $$T(n) = 4T(\dfrac n2) + 1$$

$$a=4$$, $$b=2$$, $$n^{\log_24}=n^2$$ is polynomial larger than the constant function 1. This is case 1 of the master's theorem.

### $$T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$$

$$a=4$$, $$b=2$$, $$\dfrac{n^2}{\log n}$$ is not polynomially smaller nor polynomially larger than $$n^2$$. None of the three cases of master's theorem can be applied. However, the extension of case 2, case 2b can be applied.

Exercise. (One minute or less) Assume that $$f(n)$$ and $$g(n)$$ are positive. $$f(n)$$ is polynomial smaller than $$g(n)$$ if and only if $$g(n)$$ is polynomial larger than $$f(n)$$.