I'm comparatively new to algorithm analysis and am taking a related course on coursera where I came accross k way merge sort.
The time complexity of 2 way merge sort is
n log2 n, of 3 way merge sort is
n log3 n and of 4 way merge sort is
n log4 n.
But, in the case of k-way the complexity is nk^2. This is because we pay attention to the merge part of the algo;
(2n + 3n + 4n...kn).
But, in case of 2, 3 and 4-way algorithms, we pay attention to the recursive call of one function;
(2T(n/2) + c.n).
Can anybody please explain why this is so? Or correct my approach to this question.