1
$\begingroup$

I have a computer program which I am trying to optimize. Suppose that I can collect random test cases which I will use to run both the original and the modified version to see if there are any speedups.

How can I calculate the sample size (number of test cases) which makes sure that the average speed-up/down I am getting is a significant one ? Any ideas is appreciated.

$\endgroup$
  • 4
    $\begingroup$ You can't "make sure" of this, you can only set the probability that, for a given effect size and alpha value, you will get significant results. Also, it isn't clear if this is what you are doing, but you should do power analysis only before collecting data, search 'post hoc power analysis' for more on this. Finally, this whole topic has been discussed a lot here; please see, e.g. this $\endgroup$ – Peter Flom Aug 27 '12 at 13:17
  • 3
    $\begingroup$ It is too often said "How many samples do I need to show a significant result." I hate hearing that. It presumes that the result is known and the data is being collected just to confirm it. Peter is absolutely right. You can determine sample size that will give you a high probability of rejecting the null hypothesis (power) WHEN THE ALTERNATIVE IS TRUE FOR A GIVEN EFFECT SIZE. This only says "IF" there is a difference of a certain magnitude we can specify a sample size large enough to detect it. $\endgroup$ – Michael Chernick Aug 27 '12 at 14:29
6
$\begingroup$

First, consider the timer you are using for observations as compared to the resolution/accuracy you need. If you are attempting to optimize routines that render in less than a second on average, the standard .NET and JAVA timers will present as much noise as information. If you're digging for optimization for longer running routines, greater than a second, the amount of observation error is quite reasonable regardless of the timer used.

Second, you need to first (apriori) establish the "level of significance" or power used in your analysis. This is the threshold you will use to 'reject' or 'fail to reject' your null hypothesis. A commonly used significance level is 5%, so I'll refer to that. In that context, you are asking what sample size provides a 5% significance level around your estimation of the mean.

You already know how to compute the average of your observations, I'll refer to it as $\tilde{x}$. Calculate the sample standard deviation as well; I refer to it as σ. The amount of "confidence" you have in your estimation of $\tilde{x}$ is a function of the standard deviation of your observations. Most often this is called "standard error" and you calculate it as $\frac{\sigma}{\sqrt{N}}$ where $N$ is the number of observations.

With an apriori estimate of σ (from a control group, prior experiment, etc), you can answer this question two ways:

  1. What is the estimate of the sample mean with 95% confidence?

    $\tilde{x}-\frac{2\sigma}{\sqrt{N}}$ and $\tilde{x}+\frac{2\sigma}{\sqrt{N}}$

  2. What is the minimum number of samples I need to estimate the sample mean with 95% confidence that is $W$ units in width?

    $N$ = $(\frac{4\sigma}{W})^2$

Hope that helps.

$\endgroup$
6
$\begingroup$

As others have said, the sample size depends on the size of the effect you are hoping to detect and the variability of your data. The rough rule is that when the treatment and control group are the same size and have a common variance $\sigma$, you need a sample of size $n=\frac{16}{\Delta^2}$, where $\Delta=\frac{\mu_{T}-\mu_{C}}{\sigma}$ for a two-sided test. The formula and its derivation can be found in the chapter on sample size from Gerald van Belle's Statistical Rules of Thumb.

$\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.