A General Method for Solving Divide-and-Conquer Recurrences.
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
The complexity of divide-and-conqure algorithms is often described by recurrence relations of the form Tn kTnc fn. The only method currently available 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 without the use of large tables.
- Theoretical Mathematics