2
$\begingroup$

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?

Thanks for your time.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Evil
    Commented Mar 10, 2016 at 6:07

2 Answers 2

Reset to default
5
$\begingroup$

Assuming that you're using some random-access model of computation (i.e., not an ordinary Turing machine) and that comparisons can be done in constant time, the algorithm you describe is linear. Each element of the final array is produced by comparing at most three elements of the original arrays, so each element of the output is produced in constant time.

Perhaps you misunderstood the question and they were actually asking about something else? Perhaps they mis-stated their question and they were trying to ask about the complexity of three-way mergesort (sorting an array by splitting into three parts, recursively sorting the parts, then merging them)? Perhaps they were just wrong.

Improve this answer
$\endgroup$
2
  • $\begingroup$ According to the interviewer, the complexity for this is greater than linear because for some elements we can do a non constant number of comparisons before that number is added to the new array. For example, suppose we have arrays a, b, c and indexes indA, indB, indC set to the begginning of each array. Then it turns our that we compare a[indA] to b[indB] and c[indC] and a[indA] is the minimum, so we increase indA and compare again. Now, imagine that this last scenario happens again and again, so b[indB] and c[indC] would be compared many times. That was his rationale. What do you think? $\endgroup$
    – Charles Ronson
    Commented Mar 13, 2016 at 5:31
  • $\begingroup$ @CharlesRonson As I say in the answer, each entry that's added into the result array is the result of at most three comparisons. The total number of entries added to the result array is linear, and each requires a constant number of comparisons, so the total number of comparisons is linear. Looking at it from the other end, each element of the input arrays has, on average, three comparisons performed on it. In the case that some input item gets compared "many" times, it means that it's very large, so the other arrays must have emptied earlier and had fewer comparisons performed on them. $\endgroup$
    – David Richerby
    Commented Mar 13, 2016 at 9:40
0
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – ryan
    Commented Aug 8, 2017 at 22:37
  • $\begingroup$ If $k=3$ it is $O(n)$. This was asked in the question, not when $k=n$. $\endgroup$
    – rus9384
    Commented Aug 9, 2017 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.