NPTEL Assignment

Question

Suppose we modify mergesort as follows. We split the input into three equal segments,
recursively sort each segment and then do a three way merge of the three sorted segments to obtain a
fully sorted output.
If we work out the recurrence for this variant, we find that the worst case complexity is O(n log3 n), as
opposed to O(n log2 n) for the usual divide and conquer that splits the input into two equal segments.
Let us call the new version 3-way mergesort. What can we say about the asymptotic worst case
complexity of 3-way-mergesort with the usual mergesort?

a) The asymptotic worst case complexity of 3-way mergesort is better than that of usual
mergesort.

b)The asymptotic worst case complexity of 3-way mergesort is the same as that of usual
mergesort.

c)The asymptotic worst case complexity of 3-way mergesort is worse than that of usual
mergesort.

d)This depends on the length and the initial arrangement of values of the input.

answer given is b.Why?

Comments

It is because both have Time Complexity maximum nlogn

but obviously 3 way merge sort more efficient than 2 way merge sort

---

=>loga(b) = logc(b) / logc(a)

=>So to get from log2(n) to log3(n) you need to multiply it by 1 / log3 2

=>In other words log2(n) = log3(n) / log3(2).

=>log3(2) is a constant [and O(cn) = O(n)], thus O (log2(n)) = O (log3(n)) or  O (nlog2(n)) = O (nlog3(n)). Basically as far as asymptotic analysis is concerned they both are equal.