3. Consider a modified mergesort algorithm so that the algorithm splits the data

Question

3. Consider a modified mergesort algorithm so that the algorithm splits the data into two parts, one of size , and one of size Write an algorithm for this modified sorting algorithm. Asymptotically analyze it by establishing a recurrence relation for the running time first, then analysing the recurrence tree of the algorithm. Note that you should separately determine upper and lower bounds or the runing tme of his algoritm, since the leaves will not be all at the same level, and thus only some of the levels are actualy flled complctely

Explanation / Answer

Algorithm:

Asymptotical analysis:

Recurrence Relation:

T(0) = 1

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

The question now is how to solve the recurrence relation. Let us 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 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).

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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