Say you have 3 algorithms, A B and C. You want to present a comparison of A B and C based on:

  • Precompute overhead (say tree building etc that occurs prior to runtime)
  • Runtime speed (say query response time)

The problem is, however, A B and C each have their own unique set of parameters that will dictate the quality of the results.

  • A has 3 parameters x, xx and xxx
  • B has 1 parameter y
  • C has 2 parameters z and zz

If A has it's parameter x increased from 10 to 50, say, then A's precompute overhead doubles, and A's runtime speed is halved.

If B has it's parameter y increased from 0 to 0.001 say, it's precompute time stays the same but it's runtime speed becomes 1/3 of it's former speed.

So each algorithm has it's own set of quirks and behaves differently, depending on how you set each algorithm's parameters.

But we are interested in comparing A B and C based on the two categories (precompute and runtime) listed above!

How can you compare algorithms A B and C?

  • 4
    $\begingroup$ en.wikipedia.org/wiki/Pareto_efficiency $\endgroup$ – Radu Curticapean Jul 16 '12 at 16:18
  • $\begingroup$ Is there some distribution over the set of parameters for each algorithms? For example, in 50% of the cases you use algorithm A with one set of parameters, and in the other 50% you use it with another set? If that's the case, you can compute the expected "precompute" and "runtime" and compare these. Alternatively, you can also compare the worst-case (i.e. find the parameters for which all algorithms run the most). I personally prefer the average case. $\endgroup$ – inquirer Jul 16 '12 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.