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