Bounds on algorithms for string generation

Abstract

The well-known lower bound of log2n! 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. © 1972 Springer-Verlag.