This question is about MergeSort algorithm: n is the length of the array. The nu

Question

This question is about MergeSort algorithm: n is the length of the array. The number of comparisons, the worst-case in big-Oh notation, of MergeSort algorithm is:___________ The recurrence for the running time of MergeSort algorithm is: T(n) = T(n/2) + 2 middot n log n T(n) = n middot T(n/2) + 1 T(n) = 2 middot T(n/2) + n if none of the above choices, what is it? What is the solution (the best answer) for the following recurrence corresponding to some 2/3-seareh algorithm? T(n) = (2/3) middot T(2n/3) + 3/2 middot n O(n) 0(n^3/2) none of the choices O(n log n) 0(n^2) Which case of the Master Theorem have you applied?:___________ Consider the following function that we will see in the context of Binary Heaps://array a(left..num] -note that this array starts at left > = 1 function examl(a, left, num) {var ini r:= left, offspring; while (r * 2 + 1)

Explanation / Answer

7.a) Merge sort uses O(n logn) comparisions in the worst case.

In merge sort, at each level of the recursion, we do the following:

1) Split the array in half.
2) Recursively sort each half.
3) Use the merge algorithm to combine the two halves together.

So how many comparisons are done at each step? Well, the divide step doesn't make any comparisons; it just splits the array in half. Step 2 doesn't (directly) make any comparisons; all comparisons are done by recursive calls. In step 3, we have two arrays of size n/2 and need to merge them. This requires at most n comparisons, since each step of the merge algorithm does a comparison and then consumes some array element, so we can't do more than n comparisons.

Combining this together, we get the following recurrence:

C(1) = 0
C(n) = 2C(n / 2) + n

To simplify this, let's define n = 2k and rewrite this recurrence in terms of k:

C'(0) = 0
C'(k) = 2C'(k - 1) + 2^k

The first few terms here are 0, 2, 8, 24, ... . This looks something like k 2k, and we can prove this by induction. As our base case, when k = 0, the first term is 0, and the value of k 2k is also 0. For the inductive step, assume the claim holds for some k and consider k + 1. Then the value is 2(k 2k) + 2k + 1 = k 2 k + 1 + 2k + 1 = (k + 1)2k + 1, so the claim holds for k + 1, completing the induction. Thus the value of C'(k) is k 2k. Since n = 2 k, this means that, assuming that n is a perfect power of two, we have that the number of comparisons made is

    C(n) = n lg n

7.b) Answer is option c T(N) = 2T(N/2) + N

For the others ,please post differnet questions

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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