4

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.

1

the recursion depth is log n/log k,

merging costs n*log k, using a min heap for log k per element

thus we come at T(n) = n* log k + K* T(n/k) which (unless I'm mistaken) becomes n log n (actually n (c_1/k+log(n))= n/k + n*log(n) but the n/k becomes insignificant in big O)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.