In the
analysis of algorithms
In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...
, 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
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
.
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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
before it produces a single output, unlike some algorithms that take polynomial time per output item.
[.] 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
Mihalis Yannakakis ( el, Μιχάλης Γιαννακάκης; born 13 September 1953 in Athens, Greece)[Christos Papadimitriou
Christos Charilaos Papadimitriou ( el, Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; born August 16, 1949) is a Greek theoretical computer scientist and the Donovan Family Professor of Computer Science at Columbia Un ...](_blank)
.
[
]
References
{{reflist
Analysis of algorithms