Post History

What is the correct cost formula for the average case in insertion sort algorithm?

I have been trying to learn about the cost of the insertion sort algorithm lately. I already understand the best case, worst case and average case formulas (eg $n-1$, $\frac{n(n-1)}{2}$, $\frac{n(n-1)}{4}$ respectively). But I saw that this formula isn't working for small numbers of $n$. If we take for example an array with a length of $n=3$ with $T(n)$ for the amount of comparison needed, we get $T_{\text{best}}(3)=3-1=2$, $T_{\text{worst}}(3)=\frac{3(2)}{2}=3$, and $T_{\text{avg}}(3)=\frac{3(2)}{4}=\frac{3}{2}=1.5$. This is very strange, since the average case is more efficient than the best case. And that is impossible. That means that $\frac{n(n-1)}{4}$ doesn't hold for this situation. So what I did was looking at the graph of these functions:

![Graph of cost formulas](https://software.codidact.com/uploads/goudvk4oqemrab3sjqukg3o7y18z)

It seems like that these formulas only works for $n\ge4$. Is that correct? So it basically means that, whenever we have a cost formula for an algorithm, it will become more accurate when $n$ goes larger?

I also came across [this page](https://math.stackexchange.com/a/1130043) that says that the formula $\frac{n(n-1)}{4}$ is actually wrong. I already didn't understand the part where he came up with the first formula:
>$\frac{1}{2}(1_{\text{element is in place}} + i_{\text{element is smallest yet}})$

According to the answer it should have been $$\sum_{i=1}^{n-1} \frac{i+1}2 = \frac{(n-1)n}4 + \frac{n-1}2 = \frac{(n-1)(n+2)}{4}$$ instead. Can someone please explain to me how he came up with this? And why the original one $\frac{n(n-1)}{4}$ wrong?