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

Personal Author(s):

• Bentley,Jon Louis
• Haken,Dorothea
• Saxe,James B.

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.

Descriptors:

• *RECURSIVE FUNCTIONS
• ALGORITHMS
• NUMERICAL ANALYSIS
• SOLUTIONS(GENERAL)

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE