我们可以将插入排序表示为递归过程，如下所示。在 顺序排序。为了对 A[1..n] 进行排序，我们递归排序 A[1..n−1] 然后将 A[n] 插入排序数组 A[1..n−1] 中。写一个 此递归插入版本的运行时间的重复周期 排序。
很明显，对数组进行排序需要 T(n-1( 次(因为我们不需要对最后一个元素进行排序(。但我不明白为什么将元素插入排序数组需要 O(n(。
假设我们有一个数组：A = 41;52;26;38;57;9;49.最坏的情况，我们必须遍历整个数组才能在数组的开头插入最后一个元素 n。但我认为，这需要 O(n-1( 时间，因为我们在数组中要经历 n-1 个元素。
你能解释一下我的错误和正确答案的逻辑吗？
没有比 O(n-1( 更好的了。 常量在大 O 表示法中被忽略。所以它的 O(n(。 您需要清除算法分析的基础知识。
你可以参考这里
https://www.geeksforgeeks.org/fundamentals-of-algorithms/#AnalysisofAlgorithms