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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.