= Solution
The cost is \b[$\Theta(n)$ arithmetic and comparison operations] under shared <lazy evaluation> and unit-cost operations on the numeric values. There are only three mapped streams and two merge nodes. Before the first $n$ output cells are produced, each node advances at most $n+O(1)$ input positions; each advance does a bounded number of operations. Producing the $n$ output cells also gives an $\Omega(n)$ lower bound.
This is <stream sharing in Hamming-number construction>. It relies on sharing the recursive list cells, and is not a bound on bit operations: multiplying or comparing arbitrarily large `Integer` values costs more as their representations grow.
Back to article page
