I want to estimate the true runtime of a class of programs that run on a platform that introduces virtualization-related variance into the runtime. Quantitatively, my goal is to be able to state the true runtimes any of the programs in the class within a confidence interval of 95% and with a margin of error of 2% based on an average of the given program's sampled runtimes.
To be able to state this, I need to know how many times I need to measure the runtime of a given program in this class to get an average runtime that is within 2% of the true runtime with a 95% confidence rating. Note that the programs under test are completely deterministic, i.e. if there was no variance it would take the same amount of time each run.
My approach is to analyze a representative example of the class of programs I'm working with and to extrapolate from there. To that end, I've measured the runtime of a representative program 7500 times and plotted the results on a histogram -- the results have a roughly normal distribution (the x-axis is runtime in seconds):
I know the formula for the confidence interval for a normal distribution is:
X ± Z * s/√n
X is the mean,
Z is the chosen Z-value,
s is the standard deviation, and
n is the number of observations
My question is this -- can I use algebra to solve for
n to determine the number of trials I would need to run to get an average runtime that is within 2% of the true runtime with a 95% confidence rating? Obviously, here the sampled average and sampled standard deviation would stand-in for the true values. My approach is the following:
1) Run a "sufficient" number of trials to get a sampled mean and standard deviation that is "close enough" to the true values.
2) Plug the results into the formula and solve for
n, e.g. if we use the sampled mean of 7.27 and a sampled standard deviation of .11 obtained from the 7500 trials, we find that we would need to run three trials and take the average runtime to obtain the desired result:
Z * s/√n <= sampled mean * .02 1.96 * .11/√n <= 7.27 * .02 n >= 2.1987... n >= 3 trials