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

Question

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

1. 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

2. 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.

3. 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.

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

Explanation / Answer

Answer 4:

Big –O notation

Using big- notation, we discard the low-order term   c n/2 and the constant factors c and 1/2,getting the result that the running time of insertion sort, in this case (n2) (n square 2).

So a reverse-sorted array is the worst case for Insertion Sort.

Answer 3

Since Best case Ao Algorithm is O(n).

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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