Analysis of Algorithms by the Contraction Method: Additive and Max-recursive Sequences

Ralph Neininger () and Ludger Rüschendorf ()
Additional contact information
Ralph Neininger: J. W. Goethe University, Department of Mathematics
Ludger Rüschendorf: University of Freiburg, Department of Mathematics

A chapter in Interacting Stochastic Systems, 2005, pp 435-450 from Springer

Abstract: Summary In the first part of this paper we give an introduction to the contraction method for the analysis of additive recursive sequences of divide and conquer type. Recently some general limit theorems have been obtained by this method based on a general transfer theorem. This allows to conclude from the recursive structure and the asymptotics of first moment(s) the limiting distribution. In the second part we extend the contraction method to max-recursive sequences. We obtain a general existence and uniqueness result for solutions of stochastic equations including maxima and sum terms. We finally derive a general limit theorem for max-recursive sequences of the divide and conquer type.

Keywords: Analysis of algorithms; parallel algorithms; limit laws; recurrence; probability metric; limit law for maxima (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-27110-9_20

Ordering information: This item can be ordered from
http://www.springer.com/9783540271109

DOI: 10.1007/3-540-27110-4_20

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().