Average Case Analysis of Gosper’s Algorithm for aClass of Urn Model Inputs
dc.contributor.author | Milenkovic, Olgica | en_US |
dc.contributor.author | Compton, Kevin J. | en_US |
dc.date.accessioned | 2006-09-08T19:09:44Z | |
dc.date.available | 2006-09-08T19:09:44Z | |
dc.date.issued | 2005-09 | en_US |
dc.identifier.citation | Milenkovic, Olgica; Compton, Kevin J.; (2005). "Average Case Analysis of Gosper’s Algorithm for aClass of Urn Model Inputs." Algorithmica 43(3): 211-244. <http://hdl.handle.net/2027.42/41350> | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/41350 | |
dc.description.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. | en_US |
dc.format.extent | 288658 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag; Springer | en_US |
dc.subject.other | Theory of Computation | en_US |
dc.subject.other | Software Engineering/Programming and Operating Systems | en_US |
dc.subject.other | Computer Systems Organization and Communication Networks | en_US |
dc.subject.other | Data Structures, Cryptology and Information Theory | en_US |
dc.subject.other | Algorithm Analysis and Problem Complexity | en_US |
dc.subject.other | Gosper’S Algorithm | en_US |
dc.subject.other | Hypergeometric Functions | en_US |
dc.subject.other | Urn Models | en_US |
dc.subject.other | Computer Science | en_US |
dc.subject.other | Computer Hardware | en_US |
dc.title | Average Case Analysis of Gosper’s Algorithm for aClass of Urn Model Inputs | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA | en_US |
dc.contributor.affiliationother | Department of Electrical and Computer Engineering, University of Colorado, Boulder, CO 80309, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/41350/1/453_2005_Article_1173.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/s00453-005-1173-y | en_US |
dc.identifier.source | Algorithmica | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.