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.

Improve this question
$\endgroup$
2
  • $\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
    Commented Sep 12, 2019 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
    Commented Sep 12, 2019 at 14:24

1 Answer 1

Reset to default
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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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