  We consider binary dispatching problem originating from object oriented
programming. We want to preprocess a hierarchy of classes and collection of
methods so that given a function call in the run-time we are able to retrieve
the most specialized implementation which can be invoked with the actual types
of the arguments. For the binary dispatching, where the methods take exactly
two arguments, logarithmic query time is possible, even if the structure is
allowed to take linear space. Unfortunately, known solutions achieving such
complexity require superlinear time for constructing the structure. Using a
different idea we are able to construct in (deterministic) linear time and
space a structure allowing dispatching binary methods in the same logarithmic
time. Then we show how to improve the query time to slightly sublogarithmic,
which is easily seen to be optimal as a consequence of some already known lower
bounds if we want to keep the size of the resulting structure close to linear.
