Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Functional programming, design and analysis of algorithms / 3 / f / Solution

A concatenation tree may contain arbitrarily many Cat and Nil nodes while denoting an empty or singleton list. For example, repeatedly wrap One x as Cat Nil previous. The output length stays one while the input size grows without bound. An arbitrary leaf could hide another One, so a correct general conversion cannot disregard unexamined branches. Output length alone therefore cannot bound the work; input size must be included.