Average Case Analysis of Gosper’s Algorithm for a
Class of Urn Model Inputs |
| |
Authors: | Olgica Milenkovic Kevin J Compton |
| |
Affiliation: | (1) Department of Electrical and Computer Engineering, University of Colorado, Boulder, CO 80309, USA;(2) Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA |
| |
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. |
| |
Keywords: | Gosper’ s algorithm Hypergeometric functions Urn models |
本文献已被 SpringerLink 等数据库收录! |
|