Past exam of the year 1 of the computer science course of the University of Oxford / 2017 / Functional programming, design and analysis of algorithms / 2 / d

The cost is $\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.