3
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ "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? $\endgroup$ – Apass.Jack Mar 5 at 3:08
  • $\begingroup$ @Apass.Jack thank you for attempting to help. I've made some edits to clarify as much as possible $\endgroup$ – Trixie the Cat Mar 5 at 3:44
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.