Domains Characterizations of 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-and-conquer recurrences. This paper focuses on a study of domains of classic divide-and-conquer sequences; it leads to a domain characterization theorem.