# Possible to use Master theorem? $T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$

The master theorem can be used in case of a recurrence relation of the form $$T(n) = aT(\frac{n}{b}) + g(n)$$

But is it possible to use the master theorem for recurrence relations of the form $$T(n) = aT(\lfloor \frac{n}{b} \rfloor) + g(n)$$?

• Well, have you tried adapting the proof of the Master theorem to this other type of recursion relations? Where did you get stuck? Nov 27, 2018 at 18:16
• @dkaeae I suspect the master theorem (no need for a capital M, by the way -- it's not somebody's name) is usually just presented as a fact, without proof. Nov 27, 2018 at 18:19
• @dkaeae You're correct. I should have looked up the proof first.
– upe
Nov 27, 2018 at 18:48

In fact, the conclusion of master theorem, which gives asymptotic approximation of the given function $$T$$ in $$\Theta$$ notation, still holds if we change the recurrence relation from $$T(n) = aT(\frac{n}{b}) + g(n)$$ to $$T(n) = aT(\lfloor\frac{n}{b}\rfloor) + g(n),$$ or $$T(n) = aT(\lceil\frac{n}{b}\rceil) + g(n),$$ or, even more generally, $$T(n) = aT\left(\frac{n}{b}+ h(n)\right) + g(n),\text{ where } h(n)\in O\left(\frac n{\log^2n}\right).$$
We use the master theorem in the context of giving upper bounds to increasing functions $$T$$. In this context, we know that $$T(n)=aT(\lfloor n/b\rfloor) + g(n) \leq aT(n/b)+g(n)$$ so any upper bound on the recurrence without $$\lfloor\cdots\rfloor$$ is also an upper bound on the recurrence with $$\lfloor\cdots\rfloor$$.