A simple master Theorem for discrete divide and conquer recurrences

Olivier Garet

The aim of this note is to provide a Master Theorem for some discrete divide and conquer recurrences: $$X_n=a_n+\sum _{j=1}^m{b}_j{X}_{\lfloor \frac{n}{m_j}\rfloor },$$ where the $m…