Average case analysis of Gosper's algorithm for a class of urn model inputs

Olgica Milenkovic, Kevin J. Compton

Research output: Contribution to journalArticlepeer-review


In this paper we perform an asymptotic average case analysis of some of the most important steps of Gosper's algorithm for indefinite summation of hypergeometric terms. The space of input functions of the algorithm is described in terms of urn models, and the analysis is performed by using specialized probabilistic transform techniques. We analyze two different types of urn model classes: one in which the input functions are assumed to be rational, and another for which a certain function of two inputs is assumed to be rational. The first set of results shows that the asymptotic complexity of the algorithm is the same within each of the two classes. The second set of results indicates that the complexity of the algorithm scales differently for the two classes of models: one can observe the logarithmic versus square root type of difference that is also present in other combinatorial models.

Original languageEnglish (US)
Pages (from-to)211-244
Number of pages34
JournalAlgorithmica (New York)
Issue number3
StatePublished - Sep 2005
Externally publishedYes


  • Gosper's algorithm
  • Hypergeometric functions
  • Urn models

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'Average case analysis of Gosper's algorithm for a class of urn model inputs'. Together they form a unique fingerprint.

Cite this