A real elementary approach to the master recurrence and generalizations

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The master theorem provides a solution to a well-known divide-and-conquer recurrence, called here the master recurrence. This paper proves two cook-book style generalizations of this master theorem. The first extends the treated class of driving functions to the natural class of exponential-logarithmic (EL) functions. The second extends the result to the multiterm master recurrence. The power and simplicity of our approach comes from re-interpreting integer recurrences as real recurrences, with emphasis on elementary techniques and real induction.

Original languageEnglish (US)
Title of host publicationTheory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Proceedings
Pages14-26
Number of pages13
DOIs
StatePublished - 2011
Event8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011 - Tokyo, Japan
Duration: May 23 2011May 25 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6648 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other8th Annual Conference on Theory and Applications of Models of Computation, TAMC 2011
CountryJapan
CityTokyo
Period5/23/115/25/11

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A real elementary approach to the master recurrence and generalizations'. Together they form a unique fingerprint.

Cite this