## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 211-244 |

Number of pages | 34 |

Journal | Algorithmica (New York) |

Volume | 43 |

Issue number | 3 |

DOIs | |

State | Published - Sep 2005 |

Externally published | Yes |

## Keywords

- Gosper's algorithm
- Hypergeometric functions
- Urn models

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics