# Term for open-ended algorithms

There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be

• enumeration of prime numbers in ascending order
• enumeration of grid points by increasing distance

For these there exist two fundamentally different techniques:

1. With one class of approaches you have to state the scope of your question up front. You'd state the upper bound for the primes you want, the maximal distance, or similar. The Sieve of Eratosthenes would fall into this category, as would an algorithm enumerating all points in a rectangle and then sorting them by distance.

2. With another class of approaches, you don't have to state the extent of the required output up front. You can see the enumeration as a lazily evaluated infinite sequence, and feed it to some other part of your code that should eventually terminate the generation once a generated output satisfies your requirements. Testing each odd number against a list of already found primes would be an example from this class.

Now I'm looking for a term to distinguish these two forms. Somehow the latter approach feels closely related to online algorithms, which is why I added that tag. But every deifnition I could find specifies an online algorithm as processing its input incrementally. There is almost no input here, unless you count the one-bit decision between “give me the next item” and “that's it, stop now” as an incremental input. Would calling this an online algorithm be appropriate, or is there a better term?

• Isn't 2 just lazy evaluation, a term you've already used in the question? – David Richerby Jul 5 '16 at 16:21
• 1) enumerator, sometimes "full iterator" 2) generator (lazy iterator). The 1) is uncommon - it is rather not explicitly stated and moreover "iterator" has second (more popular) meaning as object that accesses iterable results. 2) generator is used to denote program that do not perform full enumeration but commonly function that can be restarted to yield more results. So the names are shadowed... So you want to distinguish "full range checker" from "enough results generator"? – Evil Jul 5 '16 at 17:41
• @DavidRicherby: I don't think “lazy evaluation” is optimal as a distinguishing name. I could evaluate the Sieve of Eratosthenes lazily as well, returning each element once I'm done marking its multiples, and I'd still have to specify the total size of the sieve up front. I feel like I'd need to get the concept of infinity into that term somehow. I guess “lazily evaluated infinite sequence” captures that idea, but it doesn't describe the algorithm. “algorithm generating a lazily evaluated infinite sequence” is beginning to get real bulky, so I hope for something more terse. – MvG Jul 5 '16 at 20:11
• @Evil: Thanks for these suggestions. Is your last sentence a question whether you understood the question correctly? If so I'd say yes, although it's more “fixed range” than “full range” I think. Or are these terms in quotation marks your suggestions for less ambiguous terms? They sound slightly non-technical, but might be perfectly adequate for some contexts, so thanks for these as well. – MvG Jul 5 '16 at 20:23
• Yes, non technical terms to be sure that we are on the same page. And I heard them in this context, but it is just one of possible descriptions. – Evil Jul 5 '16 at 20:30

A $O(f(n))$-time delay algorithm is guaranteed to output a stream of answers, with a delay of at most $O(f(n))$ time between answers. One consequence is that outputting $k$ answers will take at most $O(k \times f(n))$ time -- but you also know that you won't ever have to wait too long for the next output. (So, this helps rule out algorithms that return the first $n$ answers very rapidly and then take a really long time to return the $n+1$th answer).