 Solution

All three denote iterate :: (a -> a) -> a -> [a], producing $x,g(x),g^2(x),\dots$. With lazy evaluation, demanding and fully evaluating the first $n$ elements costs $\Theta (n)$ for f1 and f2, and $\Theta (n^2)$ worst-case for f3, under the unit-cost application assumption.

In f1 the next state is obtained with one new application of g. In f2, the shared binding xs points back to the already generated list; each new element maps g over a shared predecessor once. In f3, the recursive f3 g x is a fresh computation. Producing output position $j$ passes through $j$ separately constructed map layers, so a strict g causes $0+1+\cdots +(n-1)$ applications. A non-strict function such as const 0 can avoid work, so the quadratic statement is a worst-case evaluation bound, not a lower bound for every possible g. Merely demanding the outer list spine without its elements is a different cost question.