A general method for solving divide-and-conquer recurrences
Jon Louis Bentley, Dorothea Haken, James B. Saxe · ACM SIGACT News · 1980
The approximate complexity of divide-and-conquer algorithms is often described by recurrence relations of the formT(n) = kT(n/c) + f(n).The only well-defined method currently used for solving such recurrences consists of solution tables for fixed functions f and varying k and c. In this note we describe a unifying method for solving these recurrences that is both general in applicability and easy to apply. This method is appropriate both as a classroom technique and as a tool for practicing algorithm designers.