# Which statistical method should I use for comparing machine run-time of two algorithms?

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.

• 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. – Brian Borchers Sep 12 '19 at 14:23
• 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. – Brian Borchers Sep 12 '19 at 14:24

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)