2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Juho Oct 11 '12 at 2:04
  • 1
    $\begingroup$ 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. $\endgroup$ – The Unfun Cat Oct 11 '12 at 13:01
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

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