# Complexity for merging 3 sorted arrays using this specific algorithtm

During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the original 3 arrays.

The algorithm is pretty basic: we set indexes at the beginning of each array and use such indexes for accessing the elements, in that fashion we find the minimum element for the 3 arrays (at the position given by the indexes) and then we insert the element into the resulting array and we increase such index. We repeat until we are done processing every element.

My answer was that the complexity was linear because we are processing n elements and we are doing a constant number of comparisions for finding the minimum element out of the 3 arrays (at the given index position). Yet, I was told that the complexity is not linear but it is higher than nlogn.

I have a few ideas but could someone explain the actual complexity of this algorithm for me?

• Merge sort is $\Theta(nlog_3n)$, but you can write $log_2n$ as this is constant. So on the part about mergesort they were wrong. If you use natural merge sort and feed three sorted arrays, this is linear (only merge phase, as runs takes whole array). – Evil Mar 10 '16 at 6:07

What you are describing is merging $K$ sorted arrays, each array of length $N$. In this case, from the algorithm you describe you are making $K$ comparisons and there is a total of $N \cdot K$ elements, your complexity is $O(N \cdot K^2)$. If $K=N$ then it is $O(N^3)$.
• You do not need to re-compare the $k$ elements every single time. Imagine sorting the $k$ elements. The first time we sort the $k$ elements, it takes $O(k \log k)$, but from there on, we only remove the minimum element. We then can take the new element and insert it and find the new minimum in $O(\log k)$ (binary search). So it really only needs to take $\Theta(n \cdot k \log k)$. This is also a lower bound. Easy to see if you imagine merging $k$ sorted arrays of length $1$ with unique elements (i.e. sort $k$ elements). – ryan Aug 8 '17 at 22:37
• If $k=3$ it is $O(n)$. This was asked in the question, not when $k=n$. – rus9384 Aug 9 '17 at 5:06