0
$\begingroup$

This is the problem:

Merge two sorted series of numbers. Their lengths are $n$ and $m$, respectively, but $n \gg m$. Your algoritm should take $O(m \log(n/m))$ comparisons.

I have come up with this algorithm:

1. Choose n/m "special" elements among n elements.
2. for i = 1 to m do
    2.1 Using binary search find block (between two special elements)
        where m_i should be inserted - time O(log(n/m))

    2.2 Using binary search in found block, find exact position for $m_i$. -                   
       O(log m)

Step 2.1 takes time $O(\log(n/m)$ and step 2.2 time $O(\log m)$, so I get in total a runtime in $O(m (\log n/m + \log m))$. How do I get rid of the $O(\log m)$ term?

Here's a sketch of the algorithm:

enter image description here

As you can see I have a problem - O(log m). How to eleminate it ?

$\endgroup$
  • $\begingroup$ I think this problem is ill-posed in at least two ways. 1) What is the definition of $\gg$? 2) I don't see how the runtime can be achieved at all without further assumptions. (See my answer.) $\endgroup$ – Raphael Jul 24 '15 at 6:38
3
$\begingroup$

What exactly does $n \gg m$ mean for your professor?

If it means $m \in o(n)$, then you are allowed $O(\log m)$ time for step 2.2. Note that $\log(n/m) = \log n - \log m$. If $m \in o(n)$, the target runtime bound simplifies to $O(m \log n)$; a summand $m \log m$ is dominated by this.

If $m \in \Theta(n)$ is allowed -- arguably, $m = n \cdot 10^{-10}$ would fulfill "a lot smaller" -- you can have that $\log n/m \in O(1)$ and the runtime bound is $O(m)$. It's quite clearly impossible to perform this task in time $O(m)$, so I think we can safely ignore this case for the purpose of this exercise.

But here is something more for you to think about.

In step 1, you need to specify "special"; if you don't pick the elements according to your sketch, the rest won't work out. So we have to select the elements $i(n/m)$. In order to do this in $o(n)$ time and perform binary search efficiently, we need the series to be stored as arrays.

We can not copy all values to a new array in the required time. We can not insert values into an array, either. So how is this to work at all?

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