在单循环有序列表中插入M个元素的时间复杂度是多少

Question

On a singly circular ordered list having N elements and 
if M elements are to be inserted what will be the complexity of time?

a) O(M*N)
b) O(M*(M+N))
c) O((M+N) * log(M+N))

我认为，做这项工作所花费的时间应该是O(N + M)。因为我们需要O(N)来找到最后一个元素，O(M)在它之后插入所有元素，并且链接需要O(1)。

---

此外，我发现Ordered这个词有点令人困惑，是Sorted还是Preserving Natural Ordering。

如果Ordered意味着Preserving Natural Ordering，那么我认为O(N + M)。

如果是Sorted，则是O(N * M)

Answer 1

这看起来像是一个排序的情况，而不是"保持自然排序"，我们将计算插入(所有m个元素(的完整操作的频率，因此，如果我们假设N的值比m 高得多，则O(m*N(似乎就是这种情况