Accession Number:

ADA064294

Title:

A General Method for Solving Divide-and-Conquer Recurrences.

Descriptive Note:

Interim rept.,

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Report Date:

1978-12-13

Pagination or Media Count:

14.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE