I understand how selection sorts work but I don't understand how the summation works mathematically in this case especially where the index j= i+1 is depending on i form the outer loop produces answer n-i-1
Please explain in detail like I have never seen a summation problem before. Thanks in advance.
Best Answer
Let's fix $i=3$ for now.
The inner sum is then $\sum_{j=4}^{n-1} 1$, i.e. $1 + 1 + \cdots + 1$ for each index $j$ from $4$ to $n-1$. There are $n-4$ addends, so this sum is $n-4$.
For a general $i \le n-1$, the inner sum $\sum_{j=i+1}^{n-1} 1 = n - i - 1$ simply because you are adding $n - i -1$ copies of the addend $1$.
The double sum just means that you perform this inner sum for every value of $i$ from $0$ to $n-1$, and then add all these sums together.