Polynomial delay
In the analysis of algorithms, 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 Johnson, Yannakakis & Papadimitriou (1988).
References
- ^ Goldberg, Leslie Ann (1993), Efficient Algorithms for Listing Combinatorial Structures, Distinguished Dissertations in Computer Science, vol. 5, Cambridge University Press, p. vii, ISBN 9780521117883.
- ^ Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos 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.