# What is "polynomial delay?"

I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with.

Here is a example sentence showing how it is used:

The loop is executed in time $O(n^2(e+n))$, which makes a polynomial delay for the output of the data.

I've tried searching a bit but I can only seem to find other papers and no definition.

• Do you have a link to the paper in question? My guess would be that it is trying to simply state that you have to wait a polynomial amount of time for the answer (algorithm to conclude).
– mdxn
Sep 26 '13 at 2:15
• So it would be a kind of synonym for polynomial complexity? Here is the paper : sciencedirect.com/science/article/pii/S0166218X00003395# Sep 26 '13 at 2:40
• Please include the reference (with author, title, year) in your question.
– Raphael
Sep 14 '16 at 8:10