TIme complexity of two reversed sorted arrays

Question

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

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

Answer 1

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).