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?
