2
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ Well, have you tried adapting the proof of the Master theorem to this other type of recursion relations? Where did you get stuck? $\endgroup$ – dkaeae Nov 27 '18 at 18:16
  • $\begingroup$ @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. $\endgroup$ – David Richerby Nov 27 '18 at 18:19
  • $\begingroup$ @dkaeae You're correct. I should have looked up the proof first. $\endgroup$ – upe Nov 27 '18 at 18:48
1
$\begingroup$

Yes, you can, as David has pointed out. However, his answer only mentions the case of the upper bounds explicitly, leaving the case of the lower bounds dangling.

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

These variants of the master theorem can be obtained by applying Akra–Bazzi method.

$\endgroup$
2
$\begingroup$

Yes, you can.

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

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