Assignment 3

---

1. In the previous assignment you were asked to consider various approaches for the \(k\)-way merge problem: creating a single sorted array efficiently out of \(k\) sorted arrays, each containing \(n\) elements. One approach considered involved examining the head of each of the \(k\) arrays to identify the next largest element, and placing this into the output array. This resulted in an operation that had a cost of \(O(k^2n)\). Given the content discussed in this module, can you propose an algorithm that uses this same basic approach, but runs in \(O(kn \log k)\) instead? State the algorithm and prove its complexity. Additionally, prove a statement of the lower bound (i.e., big-omega) of its space complexity, accounting for both \(k\) and \(n\) (i.e., \(S(n, k)\)).

Examining the heads of each of the \(k\) arrays requires time \(\Theta(k)\) to determine the minimum (or maximum). If a heap is used instead then the time is reduced to \(\Theta(\log k)\).

Push the values at the head of each array into a min heap and then pop from the heap to determine the next element to copy into the sorted output array.

Each of the \(kn\) elements in the input arrays must be pushed onto the heap once (\(\Theta(\log k)\)) and popped from it once (\(\Theta(\log k)\))

\(T(n, k) = \underbrace{kn}_{\text{elems}} \times (\underbrace{\Theta(\log k)}_{\text{push}} + \underbrace{\Theta(\log k)}_{\text{pop}}) = \Theta(kn \log k)\)

Space complexity

The non-heap \(k\)-way merge requires \(kn\) space to store the output. This heap implementation of \(k\)-way merger requires in addition \(k\) space for the heap.

\(S(n, k) = \underbrace{kn}_{\text{output array}} + \underbrace{k}_{\text{heap}} = \Theta(kn)\)

As a result, any lower bound that is at least as small as \(\Omega(nk)\) is valid.

---