用于排序数组插入的 Big O 运行时（初学者）

Question

将项目插入排序数组的 Big O 运行时间是 O(N)

但是，我想知道为什么它不是 O(N^2) 因为你不必先 找到正确的索引来放置 O(N) 的插入项，然后将其余数据向下移动一位以为插入的项腾出空间，这也是 O(N)?

Answer 1

不，那是 O(N) + O(N)，它仍然只是 O(N)。