Merging two sorted arrays $A_1$ and $A_2$ with $n_1$ and $n_2$ elements, respectively, takes $O(n_1+n_2)$ time. This strategy begins by merging two arrays of size $n$ to create an array of size $2n$. It then merges that with an array of size $n$,and so on. Thus, the running time is
$(n+n)+(2n+n)+(3n+n)+...+((k-1)n+n)) \tag{1}$ $=2n+3n+4n+...+kn\tag{2}$ $=O(k^2n)\tag{3}$
Why is the complexity of above $O(k^2n)$?
Can anyone explain mathematically how we can go from (1) to (3)?
It goes from (1) to (2), then from (2) to (3).
If you want to bypass (2), you can do this:
(1) is
$\begin{array}\\ \sum_{j=1}^{k-1} (jn+n) &=\sum_{j=1}^{k-1} (j+1)n\\ &=n\sum_{j=1}^{k-1} (j+1)\\ &=n\sum_{j=2}^{k} j\\ &=n\left(\frac{k(k+1)}{2}-1 \right)\\ &<nk^2\\ &=O(nk^2)\\ \end{array} $