Question 1: In the following questions, when asked true or false, explain your a

Question

Question 1: In the following questions, when asked true or false, explain your answer.

1. What is the difference between the worse case and best case running time of Mergesort?

2. True or false: Let Ai and Ai+1 be the i largest and the i + 1 largest elements in A. Any algorithm for sorting (based on comparisons) must compare Ai and Ai+1 .

3. What has to happen so that the maximum and minimum in an array will be compared during Quicksort? Assume that the numbers are pairwise different.

4. Let A be an algorithm for a problem that runs in O(n 2 ) and A0 an algorithm for the same problem that runs in O(n). True or false: Algorithm A0 runs better than A0 in practice.

5. What is the running time of insertion sort on a sorted array? On an array sorted in reverse?

Explanation / Answer

Multiple Questions : ANswering 1st

1 . Both the worst case and the best case running time of Merge Sort is O(nlogn). Hence no difference in the running time.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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