插入排序分析和求和符号(Insertion sort analysis and summation

我想了解插入排序的最坏情况分析，我有参与的数学问题幻灯片21（PPT） 。

据我所知，第一个公式：

但这些我挣扎：

1. 为什么会出现- 1在结束了吗？
   
2. 另外，我不明白这一个：
   

Answer 1:

这是高斯伎俩来概括号码从1到n：

第一个公式

然而，要计算总和开始于2 ，而不是1 ，这就是为什么你必须减去第一项（即1）式中：

第二个公式

从本质上讲，你计算从1相加，直到（N-1）。 如果替代n高斯招用n-1您会收到他们使用第二个公式。

您还可以看到这与指数的转换：

正如你所看到的，我已经调整了总和的边界：两个总和的上限和下限已经降低了1实际上，这deceases的总和所有条款1，纠正这一点，你必须添加1到Σ下的术语： (j-1) + 1 = j 。

Answer 2:

Σ(j=2 to n) j=n(n+1)/2-1开始于2，而不是1。因此，它是加在一起，除了1相同的术语所以总和为1以下。

Σ(j=2 to n)(j-1)是加在一起作为相同术语Σ(j=1 to n-1)(j) 。 因此，要找到其总和替换n与n-1中的式n(n+1)/2 。

文章来源: Insertion sort analysis and summation notation