A Simple but Powerful Extension of the Master Theorem for Divide-and-Conquer Sequences
Michaël Guedj · HAL (Le Centre pour la Communication Scientifique Directe) · 2021
Divide-and-conquer is a popular strategy to design algorithms. It splits the input into several smaller subproblems, solving each subproblem separately, and then combine together to solve the original problem. The analysis of such divide-and-conquer algorithms naturally leads to divide-andconquer recurrences. This paper proposes an asymptomatic theorem for divide-and-conquer sequences, that naturally extends the so-called Master Theorem.