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)$?
3
-
$\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$– dkaeaeNov 27, 2018 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 RicherbyNov 27, 2018 at 18:19
-
$\begingroup$ @dkaeae You're correct. I should have looked up the proof first. $\endgroup$– upeNov 27, 2018 at 18:48
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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$.
answered Nov 27, 2018 at 18:17