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

Measure the work of producing the entire output list, with constant-cost labels. Count height in levels, so a leaf has height one and $h=0$. A perfect ternary tree with $h+1$ levels hasvertices. This is the finite geometric series formula, used without a new proof.

The three recursive calls cost $3T(h-1)$. Ordinary concat = foldr (++) [] copies each immediate child result once, and each result has $N_{h-1}$ elements. Consequently the nonrecursive work is $\Theta (3N_{h-1}+1)=\Theta (3^h)$, givingUnroll this recurrence relation. At level $j$, the cost is $3^j\Theta (3^{h-j})=\Theta (3^h)$, and there are $h$ internal levels, followed by $3^h$ leaves. ThereforeFor $h\ge 1$ this is conventionally written $\Theta (h{3}^h)$; in terms of total size it is $\Theta (N_h\log N_h)$. The extra height factor comes from copying labels at successive ancestors, even under lazy evaluation when the whole output is demanded. Merely producing its first constructor is a different cost question. If height instead counts edges, the source's height $h+1$ means $h+2$ levels; shifting the index by one leaves the boxed asymptotic bound unchanged. Part (c)'s suffix-passing implementation avoids this repeated copying.