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?