# Merging $k$ sorted lists in $O(n\log k)$ time

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?

• Big O notation hides constants. That's its entire point. – Yuval Filmus Sep 7 '18 at 22:59
• 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). – ScottK Sep 7 '18 at 23:32
• @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). – Hello Sep 8 '18 at 4:53

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