first off apologies if this is a terrible question, but I am in a bit of a bind.
I have a problem I am trying to explain. n is the length of a list that is being sorted and the list shrinks by one every time the algorithm performs an iteration. The formula $\frac{n * (n-1)}{2}$ describes the number of comparisons the script makes.
Basically, I have a formula: $\frac{n*(n-1)}{2}$ and I am trying to explain the dividing by 2
Now, I can explain it logically in a sentence but I want to say it in a mathy way too.
if $n$ was $4$ it works out like: $$\frac{3+2+1+0}{4 * 3}$$ which works out to the half.
$$\frac{(n-1)+(n-2)+(n-3)+(n-4)}{n * (n-1)} = \frac{1}{2}$$ ( the first half of this is home many comparisons are made with a shrinking list, and its divided by how many comparisons would be made if the list didn't shrink)
But, how do I write this in a generic way?
Like, $\frac{(n-1)+(n-2)... (n-?)}{n * (n-1)} = \frac{1}{2}$ or something - the question mark is where I am having the trouble.
Thanks
HINTS:
You're actually overthinking it.
Notice that each element you take out needs zero comparisons during insertion into second list (since you'll be appending at the end for an ascending sort).
Now, counting the number of comparisons for extracting the lowest element at each iteration:
The $\color{blue}{1}$st element needed $(n-\color{blue}{1})$ comparisons.
The $\color{blue}{2}$nd element needed $(n-\color{blue}{2})$ comparisons.
The $\color{blue}{3}$rd element needed $(n-\color{blue}{3})$ comparisons.
Can you spot a pattern?
Can you derive an expression for the $r$-th term?