# How to go about working the average case run time of this trivial algorithm (and other algorithms)?

This is a similar algorithm to one I used in a previous question, but I'm trying to illustrate a different problem here.

for (int i = 0; i < numbers.length - 1; i++) {
for (int j = i + 1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == 10) {
System.out.println(i+" and "+j+" add up to 10!");
return;
}
}
}
System.out.println("None of these numbers add up to 10!");
return;


Basically, I realised, that I have a decent understanding of how to work out the best case run time here. I.e. the first two numbers which are fed in, add up to 10, and therefore our best-case runtime is constant time. Also, I understand that in the worst-case, none of the numbers we provide add up to 10, so we must then iterate through all loops, giving us a quadratic runtime. However, in the slides I was going through (for this particular course) I noticed that I had missed this:

Average case

• Presume that we've just randomly given integers between 1 and 9 as input in numbers to our previous example

• Exercise: Work out the average running time

I realise I don't have the first clue as to how to go about calculating average case run-time. I'm not asking for the answer to: "what is the average-case runtime for this algorithm?", what I need to know is, how do you work something like this out?

• I think it would be better to make this question concentrated only on the particular case and algorithm you present. I think it would be better to ask for average-case analysis methods in general in another question. – Juho Oct 11 '12 at 2:04
• I too would be interested in a survey thread about average cases. Finding worst case running times is technique, finding the average case is an art. – The Unfun Cat Oct 11 '12 at 13:01

Here's an elaboration of The Unfun Cat's answer. For convenience, let the numbers be $v_1,\ldots,v_n$. Whatever the value of $v_1$ is, for $i>1$ we have $\Pr[v_i = 10-v_1] = 1/9$. Therefore, the number of iterations of the second loop is roughly distributed geometrically $G(1/9)$, so we expect it to run about $9$ times. A complication is that $n$ is not infinite, but this doesn't have a great effect on the running time.
Given $n$, the probability that the outer loop doesn't terminate on the first iteration is $(8/9)^{n-1}$. If it does, then the expected number of (inner-loop) iterations is less than $9$. Otherwise, it is at most $\binom{n}{2}$. Therefore the running time is $O(9 + \binom{n}{2}(8/9)^{n-1}) = O(1)$, using $n^2 = O((9/8)^n)$.
You need to compute the probability $p$ that two integers between one and nine add to ten. Then solve $p*x=1$ and $x$ is the number of iterations done on average. This is a constant $c$, so the running time on average is $O(1)$.