for(int i = 0; i < n; i++){ for(int j = 0; j < i; j++){ // constant time operations }}
This was the only question I got wrong on the final quiz. I don’t understand where the /2 comes from.
It says the answer is n(n-1)/2. I thought you would have it over 2 if we were adding the iterator by 2 instead of one, then it would be n/2 instead of n. But that is not happening here. What is causing it to be over 2?
Hi @nilesmac,
This /2 comes from a mathematical proof by induction method. However, there’s a simple way to understand this problem and I have always liked this way.
Write the series twice, with the second time having the terms in reverse order.
1 + 2 + 3 + … + (n-2) + (n-1) + n
n + (n-1) + (n-2) + … + 3 + 2 +1
Now add the two series together term by term.
(n+1) + (n-1+2) + (n-2+3) + … + (3+n-2) + (2+n-1) + (1+n)
= (n+1) + (n+1) + (n+1) + … + (n+1) + (n +1) + (n+1)
You have added (n+1) a total of n times, so the sum is n(n+1).
You added the series twice, so adding the series once will give you n(n+1)/2
Hope this answer helps. Thanks.