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

Abstract

The complexity of divide-and-conqure algorithms is often described by recurrence relations of the form T(n) = kT(n/c) + f(n). 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 13, 1978
Accession Number
ADA064294

Entities

People

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

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Classification
  • Computational Complexity
  • Computer Programming
  • Computer Science
  • Computers
  • Equations
  • Four Dimensional
  • Information Processing
  • Mathematics
  • Military Research
  • Monotone Functions
  • New York
  • Security
  • Template Patterns
  • Three Dimensional

Fields of Study

  • Mathematics

Readers

  • Climatology
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)
  • Graph Algorithms and Convex Optimization.