Question 1. (5 points) If the merging algorithm used in mergesorting is implemen

Question

Question 1. (5 points) If the merging algorithm used in mergesorting is implemented inefficiently and makes N log N comparisons rather than V, then the time complexity of the resulting mergesort would be (choose the best answer) 1. O(Nlog(log N))) 2. O(N log N) 3. O(Nlog N log(log N)) 4. O(N(log N)2) 5. O(N(log(log N))2) Question 2. (5 points) If the merging algorithm used in mergesorting is implemented inefficiently and makes NVN comparisons rather than N, then the time complexity of the resulting mergesort would be (choose the best answer) 3. O(N2) 4. O(N2 log N) Question 3. (5 points) Which one of the choices below correctly ranks the functions listed by increasing order of growth (i.e., the slowest-growing first, the fastest-growing last)? I. (log logn)·ym (log n)0.7, log(n!), nl.l, n2, 2n, n! 2. (log n)0.7, (log logn)2·n, nl.l, log(n!), , 2", n! 3. (log n)0.7, (log log n)2, vT, log(n!), n11, n2, 2", n! 4. (log log n)2, (log n)0.7, Vn, log(n!), ni.l, n2, 2n, n! 5. (log log n)2, (log n)0.7, vT, n11, log(n!), n2, 2", n! Question 4. (5 points) This question is about the binary heap, using an array representa- tion as covered in class. Assume an initially empty heap on which the following operations are carried out (in that order) insert H, insert W, insert L, insert E, remove max, insert R, insert C, insert Q, remove max, insert A, insert B, remove mazx

Explanation / Answer

Hi,
There are many different questions in this, as per chegg policy, we are supposed to answer only one per answer, please post others as a separate question, we will be happy to assist you :)
Answering the 1st one,
1. To answer this, lets understand the ideal time complexity of merge sort, it has 2 parts,
a. divide
b. conquer i.e merge
divide step takes O(log N) and merging takes O(N) if implemented ideally, the total complexity is O(N*log N)
now given merge takes O(N log N) hence the total complexity is O(N log N * log N) = O(N * (log N)2)

Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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