A Simple but Powerful Extension of the Master Theorem for Divide-and-Conquer Sequences

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