Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / d / iii / Solution

Restrict the unknown function to the $n$ possibilities $f^{(i)}(x)=1$ if $x_i=1$, and $2$ otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all $n$ possibilities. A binary decision tree of depth $q$ has at most $2^q$ leaves, so $2^q\ge n$. Therefore $q\ge \lceil {\log }_{2}n\rceil =\Omega (\log n)$. Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed $d$.