Consider INSERTION SORT algorithm that takes an array of size n and sorts this array in...

 

Transcribed Image Text:

Consider INSERTION SORT algorithm that takes an array of size n and sorts this array in non-decreasing order as follows. Algorithm: INSERTIONSORT Input: An array A[1..n] of n elements. Output: A[1..n] sorted in nondecreasing order. 1. for i 2 to n 2. x ← 3. 4. 5. 6. 7. A[i] j ← i - 1 while (j> 0) and (A[j] > x) A[j+1] → A[j] j← j - 1 end while A[j+ 1] x 8. 9. end for 1. (5 points) What is the best case time complexity of this algorithm? Justify your answer. 2. (5 points) What is the worst case time complexity of this algorithm? Justify your answer. 3. (5 points) What is the space complexity of this algorithm? Justify your answer. Activate Windows Go to Settings to activate Windows. Consider INSERTION SORT algorithm that takes an array of size n and sorts this array in non-decreasing order as follows. Algorithm: INSERTIONSORT Input: An array A[1..n] of n elements. Output: A[1..n] sorted in nondecreasing order. 1. for i 2 to n 2. x ← 3. 4. 5. 6. 7. A[i] j ← i - 1 while (j> 0) and (A[j] > x) A[j+1] → A[j] j← j - 1 end while A[j+ 1] x 8. 9. end for 1. (5 points) What is the best case time complexity of this algorithm? Justify your answer. 2. (5 points) What is the worst case time complexity of this algorithm? Justify your answer. 3. (5 points) What is the space complexity of this algorithm? Justify your answer. Activate Windows Go to Settings to activate Windows.

Answer rating: 100% (QA)

The image youve provided outlines the Insertion Sort algorithm along with three questions regarding ... View the full answer