Bounds on algorithms for string generation

Summary The well-known lower bound of log₂n! on the number of comparisons required to sort n items is extended to cover algorithms, such as replacement selection, which produce a sorted string whose length is a random variable. The case of algorithms which produce several strings is also discussed and these results are then applied to obtain an upper bound on the length of strings produced by a class of string generation algorithms.The authors would like to thank Professor R. Floyd for a stimulating discussion at an early stage in this work.