Combinatorial Solutions of Multidimensional Divide-and-Conquer Recurrences.

Abstract

In this paper we use combinatorial techniques to solve recurrence relations in two variables of the form T(N,k) = 2 T(N/2,k) + T(N,k-1) + f(N) and related recurrences. These recurrences arise in the analysis of algorithms based on a paradigm called multidimensional divide-and-conquer. The analyses that we present are interesting from a combinatorial view, and show that certain algorithms are very efficient. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 29, 1979
Accession Number
ADA074499

Entities

People

  • Louis Monier

Organizations

  • Carnegie Mellon University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Atmospheres
  • Binomials
  • Boundaries
  • Computer Science
  • Computers
  • Databases
  • Efficiency
  • Equations
  • Interpolation
  • Mathematics
  • Preprocessing
  • Sequences
  • Spectra

Fields of Study

  • Computer science

Readers

  • Materials Science and Engineering.
  • Operations Research
  • Statistical inference.