A simple master Theorem for discrete divide and conquer recurrences

Publication date 27 February 2019

Abstract: 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 p_j n floor},

where the

p_{i}

's belong to

(0, 1)

. 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 g e 0}

, for example such that

s u p_{n g e 1} m a t h b b E (| a_{n} |) < + i n f t y

.

This page was built for publication: A simple master Theorem for discrete divide and conquer recurrences