2
$\begingroup$

This question is based on a solution of Laura Toma to a question from CLRS (#6 on the sheet).

Question: Give an $O(n\lg k)$-time algorithm to merge $k$ sorted lists into one sorted list, where $n$ is the total number of elements in all the input lists. (Hint: use a min-heap for $k$-way merging.)

Solution: The straightforward solution is to pick the smallest of the top elements in each list, repeatedly. This takes $k − 1$ comparisons per element, in total $O(k · n)$. As the hint suggests, the idea for the “improved” solution is to keep the smallest element from each list in a heap; each element is augmented with the index of the lists where it comes from. We can perform a DeleteMin on the heap to find and delete the smallest element and insert the next element from the corresponding list. Analysis: It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.


So I understand everything that's going on here. I just have one little question about this part:

$$O(k+n\lg k)=O(n\lg k)$$

The solution states:

It takes $O(k)$ to build the heap; for every element, it takes $O(\lg k)$ to DeleteMin and $O(\lg k)$ to insert the next one from the same list. In total it takes $O(k + n \lg k) = O(n \lg k)$.

So in my head I want to do something like this:

$$O(k+n(2\lg k))=O(k+n\lg k)=O(n\lg k)$$

Is this also correct since there are two instances of $O(n\lg k)$? Is the solution just skipping over that one part assuming it's trivial?

$\endgroup$
  • $\begingroup$ Big O notation hides constants. That's its entire point. $\endgroup$ – Yuval Filmus Sep 7 '18 at 22:59
  • $\begingroup$ Neither k nor n are constants wrt to the analysis so I think it requires some justification to remove it in this step O(k+nlgk)=O(nlgk). We can assume that k bounded by n. If k >> n, then most would be empty, and after the first pass to fill your heap, you would never look at those other lists again again, and so there is a single pass of k first looks at each queue, but after than you only touch a queue after removing its entry from the heap. So the k term is bounded by n. So O(k+n lgk) = O(n+n lgk) = O(n lgk). $\endgroup$ – ScottK Sep 7 '18 at 23:32
  • $\begingroup$ @YuvalFilmus That doesn't answer the question. I understand that the Big O notation rids constants, but before doing so, I want to make sure that for this particular problem there initially is a constant of 2 (which will be disregarded later on). $\endgroup$ – Hello Sep 8 '18 at 4:53
1
$\begingroup$

Yes, you are right.

$O(c \cdot f(n)) = O(f(n))$ for any constant $c$.

It may also be written (maybe even more clear) in the form $$O(k) + O(n \lg k) + O(n \lg k) = O(n \lg k)$$

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