# Polynomial delay

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Polynomial_delay
> Markdown URL: https://mediated.wiki/source/Polynomial_delay.md
> Source: https://en.wikipedia.org/wiki/Polynomial_delay
> Source revision: 989707068
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In the [analysis of algorithms](/source/analysis_of_algorithms), an [enumeration algorithm](/source/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](/source/worst_case).<ref name="g09">{{cite thesis|degree=PhD|publisher=University of Edinburgh|hdl=1842/10917|url=https://era.ed.ac.uk/handle/1842/10917|title=Efficient algorithms for listing combinatorial structures|first= Leslie Ann|last=Goldberg|authorlink=Leslie Ann Goldberg|date=1991|id={{EThOS|uk.bl.ethos.651566}}|website=ed.ac.uk|oclc=246835963|isbn=9780521117883}}</ref>
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](/source/exponential_time) before it produces a single output, unlike some algorithms that take polynomial time per output item.<ref name=johnson>{{citation
 | last1 = Johnson | first1 =. S. | author1-link = David S. Johnson
 | last2 = Yannakakis | first2 = M. | author2-link = Mihalis Yannakakis
 | last3 = Papadimitriou | first3 = C. H. | author3-link = Christos Papadimitriou
 | doi = 10.1016/0020-0190(88)90065-8
 | issue = 3
 | journal = Information Processing Letters
 | mr = 933271
 | pages = 119–123
 | title = On generating all maximal independent sets
 | volume = 27
 | year = 1988}}.</ref> 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](/source/David_S._Johnson), [Mihalis Yannakakis](/source/Mihalis_Yannakakis) and [Christos Papadimitriou](/source/Christos_Papadimitriou).<ref name=johnson/>

==References==
{{reflist}}

Category:Analysis of algorithms

---
Adapted from the Wikipedia article [Polynomial delay](https://en.wikipedia.org/wiki/Polynomial_delay) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Polynomial_delay?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.