Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Imperative programming (resit) / 2 / b

Scan candidate output integers in increasing order while maintaining the smallest possible witness:

spectrum(r,n):
    k = 1
    for i = 1,...,n-1:
        while r*k*k < i*i:
            k = k+1
        if r*k*k < (i+1)*(i+1):
            Out.Int(i)

The inner loop supplies the left inequality from part (a), and the final test checks the strict right inequality. This prints each qualifying integer once. The witness index never decreases and is at most $i$ after the inner loop, so its total number of increments is at most $n-1$. Consequently the whole nonrecursive program uses $O(n)$ integer arithmetic operations, not $O(n)$ iterations of a fresh search. Exact products or overflow-safe comparisons are required; arbitrary-precision bit costs depend on operand sizes.