3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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:

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

  2. 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.

  3. A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.

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