Paul Crowley

Hmmm... I don't understand how/if you can evaluate such an algorithm generically, i.e. without reference to particular metrics. I take it that the worst-case runtime is something pretty boring, and you are looking for good average runtime for metrics of interest. This presumably depends on some statistical properties of your metric, such as dimensionality, continuity, distribution etc. Again i'm guessing that these properties are rarely explicit and often poorly understood, so failing that your best bet is probably the experimental approach that you are taking.