Question

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$

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top