Distance metric for algorithms

Question

I am currently working on a project in which I need to quantify the (dis)similarity between algorithms - that is, I have a few tens of algorithms that are used for the same purpose and I would like to quantify which ones are closest (i.e., more similar) to others, and which are truly 'novel'.

Both my Google-Fu and my SO-Jutsu have failed me, so I would appreciate if anyone could shed a light on this. Does such a metric even exist?

Answer 1

As one measure of similarity, you could create n datasets, somewhat intelligently constructed, and then run each of your algorithms on all of these datasets. You then get an n-dimensional vector of runtimes associated with each algorithm, which you can then slap any old distance on. I'd imagine something like cosine distance would be a good first guess, since if your datasets are of various sizes you would sort of be classifying your algorithms by the way that they scale. In addition to runtimes, you could monitor maximum memory usage or whatever else you can think of measuring.