我有一个简单证明的问题: 证明如果array是7排序和11排序的时间,则InsertionSort的时间为O(n)。
k sorted: for every i A[i] <= A[i+k]
我认为7和11都是素数这一事实很重要。
同样是num of swaps = num of inversions
,所以如果我要证明:对于每个元素num of inv < some const num
,时间复杂度将是O(some const num * n)
,所以O(n)
。
但是我不知道该怎么做。