patternMinor
Master Theorem and rounding up to the nearest integer
Viewed 0 times
thenearestmastertheoremandintegerrounding
Problem
For the master theorem for recurrences of the form
$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$
what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/b$? My guess is that this would only allow splits that are natural numbers, and obviously you can't split into a non-integer number, but I can't see anything beyond that.
$$T(n) = a\,T\!\left(\tfrac{n}{b}\right) + f(n)\,,$$
what difference would it make if the split was into calls of $\lceil n/b\rceil$ instead of $n/b$? My guess is that this would only allow splits that are natural numbers, and obviously you can't split into a non-integer number, but I can't see anything beyond that.
Solution
Yes, this is generally valid. Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.
Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:
-
Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).
-
Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.
So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:
$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$
The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.
-
A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.
Why is this valid? Let me give three explanations, in order of decreasing amount of hand-waving:
-
Informally, it probably won't make much difference, and probably not enough to change the asymptotics. Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).
-
Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$. Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.
So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$. What about other values of $n$ that aren't a power of $b$? Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$. Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$. Then we know that $T(n)$ is bounded within a narrow range:
$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$
The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.
-
A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.
Context
StackExchange Computer Science Q#61260, answer score: 6
Revisions (0)
No revisions yet.