递归版插入排序的运行时间递推式及插入操作时间复杂度疑问

首先给出递归插入排序的运行时间递推式：

• 当数组长度为1（n=1）时，数组本身已是有序状态，无需额外排序操作，基础情况为：T(1) = Θ(1)
• 当数组长度n>1时，我们先递归排序前n-1个元素（耗时T(n-1)），再将第n个元素插入到已排序的前n-1个元素中（这一步耗时Θ(n)），因此递推式为：T(n) = T(n-1) + Θ(n)

接下来咱们拆解为什么插入步骤的时间复杂度是O(n)——用你提到的类似数组举个实际例子：
假设已经递归排序好的前n-1个元素是[41, 52, 63, 74, 85]，现在要插入的元素是30（这是最坏情况：插入元素比已排序数组里所有元素都小）。
这时候我们需要完成这些操作：

• 从已排序数组的末尾开始比较：30和85比，30更小，把85往后移动一个位置；
• 接着拿30和74比，还是小，74也后移；
• 继续和63、52、41依次比较，每一次都要把当前元素后移一位；
• 直到遍历完所有已排序元素，最后把30放到数组的第一个位置。

在这个最坏场景下，我们一共做了n-1次比较操作，还有n-1次元素移动操作，总的操作次数和n成正比，也就是Θ(n)级别。就算是最好情况（比如要插入的元素是90，比所有已排序元素都大，直接放到末尾，只需要1次比较），但分析算法时间复杂度时通常关注最坏情况或平均情况，这里插入步骤的时间复杂度上限是O(n)，所以递推式里我们用Θ(n)来表示这部分耗时。

内容的提问来源于stack exchange，提问作者DY92