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

Question

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?

Answer 1

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

Answer 2

An insight here is that the probability of returning early does not depend on the length of the input (as long as numbers.length is of such a size that you would expect to find two numbers that add to ten).

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

In general you would need to evaluate the running time of your algorithm on random inputs (for a specific probability distribution) and find the average. This can be tricky.

Wikipedia has a nice example for quicksort.