4. Suppose we sort an array of numbers, but it turns out every element of the ar

Question

4. Suppose we sort an array of numbers, but it turns out every element of the array is the same, e.g., {17, 17, 17, ..., 17}. (So, in hindsight, the sorting is useless.)

a) What is the asymptotic running time of insertion sort in this case?

b) What is the asymptotic running time of selection sort in this case?

c) What is the asymptotic running time of merge sort in this case?

d) What is the asymptotic running time of quick sort in this case?

e) Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which insertion sort takes O(n) time. What if the list is reversed?

Please give some explination as to why, but it dosen't need to be an essay.

Explanation / Answer

a) What is the asymptotic running time of insertion sort in this case?
Answer: O(n)
Explanation: For Sorted Input Insertion Sort takes O(n) time. The control will not go into while loop and hence only the outer loop will run. Hence the time complexity is O(n)

b) What is the asymptotic running time of selection sort in this case?
Answer: O(n2)
Explanation: both the loop will run irrespective of the input. Selection sort will run in the usual way and hence the time complexity is O(n2)

c) What is the asymptotic running time of merge sort in this case?
Answer: O(n log n)
Explanation: Merge Sort will divide the array into two halfes irrespective of the input.. Merge Sort  will run in the usual way and hence the time complexity is O(n log n)

d) What is the asymptotic running time of quick sort in this case?
Answer: O(n2)
Explanation: Quick Sort for sorted input takes O(n2). As the partition will take with 1 and n-1 element.

e) Give an example input list for which merge-sort and heap-sort take O(n log n) time, but for which insertion sort takes O(n) time. What if the list is reversed?

Input : 1 2 3 4 5
Insertion Sort will take O(n) time if the list is Sorted
What if the list is reversed? : If the list is reversed, then it will take O(n2)


Thanks, please let me know if there is any concern. PLEASE UPVOTE if helpful

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

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