Consider a modified mergesort algorithm which splits the data into two parts, on

Question

Consider a modified mergesort algorithm which splits the data into two parts, one of size (n/3), and one of size (2n/3). Write an algorithm for this modified sorting algorithm, and asymptotically analyze it by establishing a recurrence relation for the running time first, then analysing the recurrence tree of the algorithm. (Note: separately determine upper and lower bounds for the running time of this algorithm, since the leaves will not be all at the same level, and so only some of the levels are filled completely)

Explanation / Answer

Let's start by writing out a recurrence relation. You'll split the problem into subarrays of size n / 3 and 2n / 3, and then in the merge step still do linear work to combine them. That gives the recurrence

T(0) = 1

T(n) = T(n / 3) + T(2n / 3) + (n)

note : - (n) time to merge (n/3) and (2n/3)

The question now is how to solve the recurrence relation. I'm going to claim that this is (n log n). To see this, we'll prove that it's (n log n) and that it's O(n log n) by using the recursion tree method.

Think about expanding out this recursion using a recursion tree. Notice that

More generally, up until the point where the n / 3 branches die off, the top layers of the tree all do (n) work. The number of layers before you start to have the recursion die off is roughly log3 n, so the work done is at least (n log n) due to (log n) layers doing (n) work.

You can also notice that the work per layer is always O(n), because the size of the subproblems is always no greater than the size of the subproblems on the previous layer (it's equal for the first few layers, then drops as those layers drop off). Therefore, an upper bound will be O(nL), where L is the total number of layers. The slowest problem to shrink shrinks by a factor of 2/3 at each layer, so there will be O(log n) total layers. This gives an upper bound of O(n log n).

Since the work is O(n log n) and (n log n), it's therefore (n log n).

Hence we can see that the best case is exactly the same as we divide the problem into 2 equal parts (and thus so must also be the average).

It is interesting to note that we will get the same results for general k-ary search (as long as k

is a fixed constant which does not depend on n ) as n approaches infinity.

T(0) = 1

T(n) = T(n / 3) + T(2n / 3) + (n)

note : - (n) time to merge (n/3) and (2n/3)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.