patternMinor
Meaning of polynomially larger or smaller in the context of the master method
Viewed 0 times
meaningthelargermethodmastersmallercontextpolynomially
Problem
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 0$ must be smaller than $f(n)$ or in other words $n^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
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 0$ must be smaller than $f(n)$ or in other words $n^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
Solution
(This answer refers to the version 6 of the question, which does not contain "my professor's response".)
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.
Let me fix the meaning of "polynomially smaller" and "polynomially larger" in the current context. There are other usages, which are not relevant here.
Meaning 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$. We will never say $f(n)$ is polynomially equal to $g(n)$.
Here are some examples.
$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.
Simple exercises
Exercise 1. Suppose $f(n)$ is polynomial smaller than $g(n)$. Show that $f(n)$ is eventually smaller than $g(n)$, i.e., there exists some constant $n_0$ such that $\lvert f(n)\rvert \lt g(n)$ for all $n>n_0$.
Exercise 2. Verify that $f(n)$ is polynomial smaller than $g(n)$ if and only if $g(n)$ is polynomial larger than $f(n)$, assuming that both $f$ and $g$ are always positive.
Exercise 3. Suppose $f(n)$ is polynomial smaller than $g(n)$. Find another function $h(n)$ such that $f(n)$ is polynomial smaller than $h(n)$ and $h(n)$ is polynomial smaller than $g(n)$.
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.
Let me fix the meaning of "polynomially smaller" and "polynomially larger" in the current context. There are other usages, which are not relevant here.
Meaning 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$. We will never say $f(n)$ is polynomially equal to $g(n)$.
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.
Simple exercises
Exercise 1. Suppose $f(n)$ is polynomial smaller than $g(n)$. Show that $f(n)$ is eventually smaller than $g(n)$, i.e., there exists some constant $n_0$ such that $\lvert f(n)\rvert \lt g(n)$ for all $n>n_0$.
Exercise 2. Verify that $f(n)$ is polynomial smaller than $g(n)$ if and only if $g(n)$ is polynomial larger than $f(n)$, assuming that both $f$ and $g$ are always positive.
Exercise 3. Suppose $f(n)$ is polynomial smaller than $g(n)$. Find another function $h(n)$ such that $f(n)$ is polynomial smaller than $h(n)$ and $h(n)$ is polynomial smaller than $g(n)$.
Context
StackExchange Computer Science Q#105149, answer score: 4
Revisions (0)
No revisions yet.