-3
$\begingroup$

If I have two sorted lists.

list A => 1 -> 2 -> 4 -> 11 -> 31
list B => 2 -> 31 -> 54

Now what should be the order of (sorted) merge and why?

According to the rule, If the list lengths are m and n, the merge takes $O(m+n)$ operations, the order should be $O(5 + 3)$. Am I right?

I would appreciate if someone help me out in understanding it.

$\endgroup$
  • 2
    $\begingroup$ Step away from $O$ for a minute, it's harmful for you, right now. It hides the issue you are having. You need to count the number of comparisons/operations, not handwave some $O$-s over it. $\endgroup$ – Raphael Aug 16 '15 at 14:17
6
$\begingroup$

You are asking:

Now what should be the order of merge and why?

First of all, we need to fix the merging algorithm. I'll assume the canonical one, i.e.

merge(A, B) {
  if ( A.size == 0 ) {
    return B
  }
  if ( B.size == 0 ) {
    return A
  }

  if ( A.head <= B.head ) {
    return A.head + merge(A.tail, B)
  }
  else {
    return B.head + merge(A, B.tail)
  }
}

Now you propose two lists:

A = 1 -> 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

So just execute the algorithm and count operations! I'll assume that you only want to count the comparison A.head <= B.head. A compacted trace of the algorithm is (unfolding the recursion)

C = 
A = 1 -> 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1
A = 2 -> 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1 -> 2
A = 4 -> 11 -> 31
B = 2 -> 31 -> 54

C = 1 -> 2 -> 2
A = 4 -> 11 -> 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4
A = 11 -> 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11
A = 31
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11 -> 31
A = 
B = 31 -> 54

C = 1 -> 2 -> 2 -> 4 -> 11 -> 31 -> 31 -> 54
A = 
B = 

So you see it took seven recursive calls (plus the main call), and six comparisons. You can easily swap the parameters and do the same; you'll get seven comparisons. So the order you have is slightly better. Do you see why?

It's advantageous if one of the lists runs empty early.

Note that the order of comparison and whether you use <= or < is crucial here; other choices may make the other order better.

Having worked through this example, you are ready to think about what the worst case inputs are.

Two lists of length $m$ and $n$ that run empty at the same time.

And then you execute the algorithm symbolically and count the number of steps necessary.

If you can never append more than one element when the other list is empty (return A resp. return B), you had to have had $n + m - 1$ recursive calls up to that point, one for each element, since you only ever pick one element per recursive call. Plus the last call, that's a total of n+m recursive calls.

Since every call does merge at least one element, there can be no more than $n+m$ recursive calls, so this is indeed the worst case.

Now you observe that each recursive call takes time $O(1)$, assuming a suitable list representation (in particular with $O(1)$-time size), and you are done.

This is not rocket science, by the way; it's rater mechanic, in fact, as our reference question explains. As an exercise, you can carry over the analysis to a more typical iterative implementation of merge.

$\endgroup$
1
$\begingroup$

O(5+3) technically is same as O(1).

What that means is that given a list of 5 elements and another containing 3 elements, they can be merged in constant time.

This is because the input size is a constant (viz. 8).

Even if you were to merge two lists of size million each, the time complexity of the resulting algorithm would still be O(1). This is because the input size is a constant.

The big O notation is helpful only when you are interested to know how the time complexity of algorithm varies with varying input size.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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