Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 3 / f / Solution

Let $m\ge 1$ be the number of real contacts, and suppose the requested name is at position $j$, counting from one. The implementation above makes exactly $j$ name-equality comparisons, including the successful comparison; null checks are not string comparisons. Thus the minimum is one, when the first real contact is requested, and the maximum is $m$, when the last is requested. The precondition excludes unsuccessful recalls and recalls on an empty book. This counts calls to string equality, not individual character inspections within each call.