Divide-and-conquer recurrences - Classification of asymptotics Academic Article uri icon

abstract

  • We deal with a class of recurrence equations arising in the theory of algorithms, stochastic pocesses, computer science, etc. and give a classification theorem for asymptotics of their solutions. The method of the proof is based upon consideration of the exponential generating function, which is a solution of a linear nonhomogeneous functional equation with rescaling.

publication date

  • January 1, 2000