Automatic analysis is useful in several instances, including finding the average number of cycles in a random permutation of n elements, determining the path length in a random heap-ordered tree of n elements (quicksort), finding the path length in a random plane tree, and symbolic differentiation algorithms. The authors present the results of their extensive investigations into the automatic average-case analysis of algorithms. The authors call their prototype system for this purpose Lambda-Upsilon-Omega (LUO).
The paper approaches the problem in two ways--algebraic and analytic. The algebraic component deals with exact counting via the use of generating functions. The analytic component uses the analytic properties of these generating functions to facilitate the capture of asymptotic information. Two early examples illustrate the key approaches used in the paper. The results are highly mathematical, using complex notations. The proofs would appeal to the mathematically sophisticated. The paper has over 90 relevant references. Most of these references are from easily accessible sources. LUO is written in the functional language CAML and the computer algebra language Maple. The paper will appeal only to the narrow group of researchers working in this area of the analysis of algorithms.