A simple master Theorem for discrete divide and conquer recurrences

Olivier Garet

paper

A simple master Theorem for discrete divide and conquer recurrences

arXiv:1902.10600

Abstract

The aim of this note is to provide a Master Theorem for some discrete divide and conquer recurrences: $X_{n} = a_{n} + j = 1 \sum m b_{j} X_{⌊ \frac{n}{m _{j}} ⌋},$ where the $m_{i}$ 's are integers with $m_{i} \geq 2$ . The main novelty of this work is there is no assumption of regularity or monotonicity for $(a_{n})$ . Then, this result can be applied to various sequences of random variables $(a_{n})_{n \geq 0}$ , for example such that $sup_{n \geq 1} E (∣ a_{n} ∣) < + \infty$ .