An Extended Big Theta 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 divideand-conquer recurrences. This paper proposes an asymptomatic theorem for divide-and-conquer sequences, extended thus the so-called Master Theorem