2
$\begingroup$

I am comparing the run-time of two algorithm by solving different instance of the problems. Sample of my data:

 problem_id  |  algo_original_time  |  algo_improved_time
---------------------------------------------------------
 prob_01     |  0.56                |  0.036
 prob_02     |  0.26                |  0.005
 prob_03     |  0.75                |  0.055
 ....

Note that, all of the problem instances are distinct and they do not have any correlation.

I have already used cross-validation plot to represent the data. Is there any better way/ statistical method to compare the run-time of this two algorithms.

$\endgroup$
  • $\begingroup$ At the level of measurement, it's seldom the case that run-time measurements are this precisely repeatable- if you ran the same problems again would you get exactly the same times? If not, then you need to quantify the variation in running times and most likely repeat runs to average out the variation. $\endgroup$ – Brian Borchers Sep 12 at 14:23
  • $\begingroup$ Are you trying to determine how much faster the one code is than the other (e.g. A is 10.6 times faster than B)? In that case it might be appropriate to use the geometric mean of the run times. $\endgroup$ – Brian Borchers Sep 12 at 14:24
2
$\begingroup$

This is a typical use case for a paired t-test. The idea is to consider only the runtime difference $\Delta t$ for each problem and test for the null hypothesis $E(\Delta t)=0$. For a step-by-step explanation, see e.g. (the article refers to segmentation evaluation, but on an abstract level the problem is identiclal to yours):

Mao, Kanungo: "Empirical performance evaluation methodology and its application to page segmentation algorithms". IEEE Transactions on Pattern Analysis and Machine Intelligence 23 (3), pp. 242-256 (2001)

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.