插入排序分析与求和表示法

我试图理解插入排序的最坏情况分析，但我对涉及的数学有疑问幻灯片 21（ppt） http://www.cse.unr.edu/%7Ebebis/CS477/Lect/InsertionSortBubbleSortSelectionSort.ppt.

我理解第一个公式：

但我正在努力解决这些问题：

1. Why is there a - 1 at the end?
   
2. Also, I don't understand this one:
   

高斯技巧是将 1 到 n 之间的数字相加：

第一个公式

但是，您想要计算的总和从2, not 1，这就是为什么您必须从公式中减去第一项（即 1）：

第二个公式

本质上，您计算从 1 到 (n-1) 的总和。如果你替代n在高斯的把戏中n-1，您会收到他们使用的第二个公式。

您还可以通过索引转换来查看这一点：

正如你所看到的，我调整了总和的边界：总和的上限和下限都减少了 1。实际上，这减少了all总和中的项除以 1，要纠正此问题，您必须将 Σ 下的项加 1：(j-1) + 1 = j.