# Master Theorem and rounding up to the nearest integer

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.

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.