Question

A $\mathit{k}\mathbf{-}$way merge operation. Suppose you have $\mathit{k}$sorted arrays, each with $\mathit{n}$elements, and you want to combine them into a single sorted array of$\mathit{k}\mathit{n}$ elements.

(a)Here’s one strategy: Using the merge procedure from Section 2.3, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of $\mathit{k}$and $\mathit{n}$?

(b) Give a more efficient solution to this problem, using divide-and-conquer.

Short answer

(a) Time complexity:$O\left(k^{2}n\right)$

(b) Time complexity:$O\left(kn\log k\right)$

Step-by-step solution

Introduction to array

There are different kinds of Array: $1,2,3$ -dimensional and multi-dimensional arrays. In the above question there will be sorted array technique through we can combine single sorted array in $\raisebox{1ex}{$k$}\!\left/ \!\raisebox{-1ex}{$n$}\right.$elements. To check that see below detail related to combine theory of array.

Step 2:Give the time complexity of the given algorithm.

(a)

Combine each of the$k$ arrays with the preceding array one after the other, for each array containing $1$to $n$entries.

Suppose that merging the array takes linear time.

Originally, the first and second arrays are combined, with each array having a size of $n$.

As a result, it takes$n\times n$ time, which equals $2n$. The next array of size$n$ is then combined with both the earlier merged array$2n$ .

As a result, merging three arrays takes$3n$ time. It is then combined with the fourth array, which takes$4n$ time.

As a result, the total time required to combine the entire array is

$\begin{array}{c}Timetaken=O(2n+3n+\dots +kn)\\ =O\left(k^{2}n\right)\end{array}$

Therefore, thetime complexity used to merge array is $O\left(k^{2}n\right)$.

                                                                                                                     Step 3:Efficient solution to perform k-way merge operation:

(b)

To begin, all $n$arrays get separated into two equal groups, each with$\frac{k}{2}$ arrays.

After that, every format's arrays were recursive combined one by one, and both sets merging array were merged together.

The issue is solved by breaking it into two smaller problems of size $\frac{k}{2}$and combining them in a constant time $nk$.

Thus$T\left(k\right)$,can be expressed as,

$T\left(k\right)=2T\left(\frac{k}{2}\right)+O\left(nk\right)$……(1)

Consider the master theorem for the following recurrence equation,

$T\left(k\right)=aT\left(\frac{k}{b}\right)+k^c$……(2)

CompareEquations (1) and (2),$k^c$ equals$nk$ ,$c$equals $1$,$b$equals$2$and $a$equals2 . If,$c={\log }_{b}a$ then perhaps the running speed is, according to master's thesis.

$T\left(k\right)=O\left(k^c\log k\right)$……(3)

Here, the value of $c=1$and the value of${\log }_{b}a={\log }_{2}2=1$which is equal to .Thus, substitute $k^c$as$nk$ in Equation (3). So, the running time of algorithm is,

$T\left(k\right)=O\left(nk\log k\right)$

Therefore, the time complexity of the algorithm in terms of $k$and $n$ is $T\left(k\right)=O\left(nk\log k\right)$.