Polynomial delay

In the analysis of algorithms, an enumeration algorithm (i.e., an algorithm for listing a large or infinite collection of structures) is said to have polynomial delay if the time between the output of any one structure and the next is bounded by a polynomial function of the input size, in the worst case.^[1] Polynomial delay implies that the total time used by an algorithm will be polynomial per output item, but is a stronger requirement. This is a desirable property, because it means that any consumer of the stream of outputs will not have to wait idle for a long time from one output to the next. In particular, an algorithm with polynomial delay cannot have a startup phase that takes exponential time before it produces a single output, unlike some algorithms that take polynomial time per output item.^[2] Additionally, unlike bounds on the total time, it is a suitable form of analysis even for algorithms that produce an infinite sequence of outputs.

The notion of polynomial delay was first introduced by David S. Johnson, Mihalis Yannakakis and Christos Papadimitriou.^[2]

References

1. Goldberg, Leslie Ann (1991). Efficient algorithms for listing combinatorial structures. ed.ac.uk (PhD thesis). University of Edinburgh. hdl:1842/10917. ISBN 9780521117883. OCLC 246835963. EThOS uk.bl.ethos.651566.
2. Johnson, . S.; Yannakakis, M.; Papadimitriou, C. H. (1988), "On generating all maximal independent sets", Information Processing Letters, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8, MR 0933271.