On the complexity of indefinite summation

We analyze the relation between the value of the dispersion and running time complexity of indefinite summation algorithms for different classes of summands, and show that the dependency of the running time on dispersion is non-essential (i.e. it is a feature of algorithms, not of the summation problems) in many cases. As an example of such behaviour we can mention  the following recent finding: if a non-rational hypergeometric term is summable, then the size of the result is polynomial in the size of the summand and we have an algorithm to find the sum in polynomial (in the input size) time.

This leads to practical improvements of the algorithms for indefinite summation, based on ideas of direct indefinite summation and succinct representation of the factorial polynomials.