Question 8695 – Sorting
April 18, 2024Question 16524 – CMI PHD 2022
April 19, 2024Question 8115 – Sorting
Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?
I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
Correct Answer: D
Question 18 Explanation:
If input sequence is already sorted then the time complexity of Quick sort will take O(n2) and Bubble sort will take O(n) and Merge sort will takes O(nlogn) and insertion sort will takes O(n).
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n)
with the help of substitution method it will take O(nlogn).
We can also use master’s theorem [a=2, b=2, k=1, p=0] for above recurrence.
→ The recurrence relation for Quicksort, if elements are already sorted,
T(n) = T(n-1)+O(n) with the help of substitution method it will take O(n2).
→ The recurrence relation for Merge sort, is elements are already sorted,
T(n) = 2T(n/2) + O(n)
with the help of substitution method it will take O(nlogn).
We can also use master’s theorem [a=2, b=2, k=1, p=0] for above recurrence.
I and II only
I and III only
II and IV only
I and IV only