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.
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. 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).