Paul Crowley

Worst-case is the metric where x != y => d(x, y) == 1, the "are we nearly there yet" metric. You always have to compare to half or all the elements with that metric. So you are exactly right. And not just properties of your metric - statistical properties of your likely dataset too. Eg if it's in n-dimensional space but tends to lie very close to a plane, then it will perform as if it lay in a 2-dimensional space.