Answer:
The overall order of complexity would be [tex]O(nk^2)[/tex]
Explanation:
For this method
time taken to merge the first two series will take a time as given in
[tex]T(1)=n+n[/tex]
For the second merge it is
[tex]T(2)=n+2n[/tex]
Similarly for the k series, the number of merges will be k-1 and the time is given as
[tex]T_{(total)}=\sum_{i=1}^{k-1}T_{(i)}[/tex]
Now the each T is given as
[tex]T_{(i)}=n+in[/tex]
[tex]T_{(total)}=\sum_{i=1}^{k-1}T_{(i)}\\T_{(total)}=\sum_{i=1}^{k-1}(n+in)\\T_{(total)}=n(\frac{k(k+1)}{2}-k)+kn\\T_{(total)}=\frac{nk(k+1)}{2}-nk+kn\\T_{(total)}=\frac{nk(k+1)}{2}\\T_{(total)}=\frac{(nk^2+nk)}{2}[/tex]
As the highest order would be of nk^2 so the overall order of complexity would be [tex]O(nk^2)[/tex]
