  In the area of query complexity of Boolean functions, the most widely studied
cost measure of an algorithm is the worst-case number of queries made by it on
an input. Motivated by the most natural cost measure studied in online
algorithms, the competitive ratio, we consider a different cost measure for
query algorithms for Boolean functions that captures the ratio of the cost of
the algorithm and the cost of an optimal algorithm that knows the input in
advance. The cost of an algorithm is its largest cost over all inputs.
Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean
functions, and dubbed it instance complexity. Grossman et al. showed, among
other results, that monotone Boolean functions with instance complexity 1 are
precisely those that depend on one or two variables.
  We complement the above-mentioned result of Grossman et al. by completely
characterizing the instance complexity of symmetric Boolean functions. As a
corollary we conclude that the only symmetric Boolean functions with instance
complexity 1 are the Parity function and its complement. We also study the
instance complexity of some graph properties like Connectivity and k-clique
containment.
  In all the Boolean functions we study above, and those studied by Grossman et
al., the instance complexity turns out to be the ratio of query complexity to
minimum certificate complexity. It is a natural question to ask if this is the
correct bound for all Boolean functions. We show a negative answer in a very
strong sense, by analyzing the instance complexity of the Greater-Than and
Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the
input size for both of these functions, while we exhibit algorithms for which
the instance complexity is a constant.
