instance optimality

@inproceedings{FaginLN01,
AUTHOR = {R. Fagin and A. Lotem and M. Naor},
TITLE = "Optimal Aggregation Algorithms for Middleware",
booktitle = PODS,
YEAR = "2001",
pages = "102-113",
}

Intuitively, instance optimality corresponds to optimality
in every instance, as opposed to just the worst case or the
average case. There are many algorithms that are optimal
in a worst-case sense, but are not instance optimal. An
example is binary search: in the worst case, binary search
is guaranteed to require no more than log N probes, for N
data items. However, for each instance, a positive answer
can be obtained in one probe, and a negative answer in two
probes.