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 &lt; numbers.length - 1; i++) {
    for (int j = i + 1; j &lt; 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?
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&gt;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)$.