What would be the time complexity of two reversed arrays merge into one sorted array?

Is it O(n) or O(log n)?

CodePudding user response：

If both of the given arrays are in reversed sorted order it would be O(m n)(m - length of 1. array, n - length of 2. array) because you need to iterate linearly through both arrays.

But if arrays are not sorted you have 2 options:

1. To sort them and after sorting to merge them O(nlogn mlogm).
2. To concatenate arrays and to sort that concatenated array O(nlogn mlogm).