World's most popular travel blog for travel bloggers.

# Master Theorem and rounding up to the nearest integer

, ,
Problem Detail:

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.

###### Asked By : Barry S

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 $n$, 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.