Let us assume that we have two algorithms, $A$ and $B$. Based on 3 different values of a parameter, $P$, $A$ takes $a_1, a_2, a_3$ seconds and $B$ takes $b_1, b_2, b_3$ seconds. What would be a proper way to measure which algorithm is more sensitive to $P$?

To address a diverse community, I will give an analogy: let us assume that depending on whether it rains heavily (value 2), mildly (1) or none(0) at all, one crop growing procedure $A$ takes $a_1, a_2, a_3$ time and another one, $B$, takes $b_1, b_2, b_3$ time. What would be a suitable statistical methodology to determine which procedure is more dependent on ("sensitive to") raining? We can also assume that:

  1. We are growing same crops with $A$ and $B$ on the same kind of field.

  2. $a_i$, $b_i$ can vary over different execution and the execution times for $A$ and $B$ are reported in terms of averages and standard deviation. $a_i$, $b_i$-s' can be averages (for each $i$-th value of $P$) or just a single execution time (for the $i$th value of $P$).

I am interested in measuring the "sensitivity" of the algorithm when the variance in the execution time of an algorithm is reported in either relative ("execution time of A increased by 5%") or absolute scale ("execution time of A increased by 5 sec") or both.

The exact problem I am working with is to compare the execution time of two distributed graph algorithms and decide which algorithm is more sensitive to underlying runtime parameters.

  • $\begingroup$ What is the nature of parameter P? Is it continuous? If A and B are continuous function of P, you can find the derivatives which is likely related to what you want. Note you can also estimate the derivatives numerically as well so you don't actually have to be able to write down the function in closed expression form. $\endgroup$ – Billiska May 11 '17 at 18:53
  • $\begingroup$ Thanks @Billiska . $P$ currently takes values in discrete form. $\endgroup$ – Jesun May 11 '17 at 19:19
  • $\begingroup$ I don't care about the analogy; please define what "sensitive" means here, and how you expect to learn anything from a sample size of three. $\endgroup$ – Raphael May 11 '17 at 19:47
  • 1
    $\begingroup$ The analogy does seem somewhat redundant: we're computer scientists so we understand what the running time of an algorithm is, without having to dress it up with unclear statements about growing crops. $\endgroup$ – David Richerby May 11 '17 at 19:58
  • 2
    $\begingroup$ And what does "varies more" mean? Is a change from 1 to 2 more or less variation than a change from 10 to 15, for example? $\endgroup$ – David Richerby May 11 '17 at 20:28

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.