Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Imperative programming / 2 / c / Solution

By the time print(n) is called, record has evaluated divisors(i) once for every $1\le i\le n$. In the unit-cost model, the total number of remainder tests isThe record values comparisons add only $O(n)$ work, and output is cheap by assumption. The elapsed time is $\Theta (n^2)$. This measures time to reach a given highly composite number, rather than time as a function of the number of printed records.