Why are you pairing the numbers? It’s really much more straightforward than that. Let
n = array.length.
The inner loop has
n-1 iterations in the first iteration of the outer loop, then
n-2 iterations in the second iteration of the outer loop etc. So the total number of steps is
(n-1) + (n-2) + ... + 1. Which of course is
I thought it was clear that
1 + 2 + ... + n = n(n+1) / 2 from high school maths. But here is an explanation.
You can formally prove the result using mathematical induction. But you can also give an intuitive and informal derivation (this is what you called “pairing”) – the story goes that the young Carl Friedrich Gauss came up with this when he was in primary school:
1 + 2 + ... + (n-1) + n = x n + (n-1) + ... + 2 + 1 = x (just the first line in reverse) (n+1) + (n+1) + ... + (n+1) + (n+1) = 2x (adding the first two lines) n(n+1) = 2x (counting the (n+1)'s) n(n+1)/2 = x (dividing both sides by 2)
Now what if we only want to count up to
n-1? If you wanted to, you could do the same trick again to derive the sum:
1 + 2 + ... + (n-2) + (n-1) = x (n-1) + (n-2) + ... + 2 + 1 = x (just the first line in reverse) n + n + ... + n + n = 2x (adding the first two lines) (n-1)n = 2x (counting the n's) n(n-1)/2 = x (dividing both sides by 2)
But actually that’s far too tedious. Since you know that
1 + 2 + ... + n = n(n+1)/2, you can just substitute
n in this formula and immediately get
CLICK HERE to find out more related problems solutions.