Which of the sorts in the textbook can be characterized by the fact that the best case will have a running time of θ(n) if the data is already sorted?
i.quicksort
II.selection sort
III.insertion sort
A)III only
B)II only
C)I only
D)I and III only

Question

Quizplus · Accepted Answer

Insertion sort has a best-case running time of θ(n) when the data is already sorted, as it only needs to compare each element once to see that it is in the correct place, resulting in linear time complexity. Quicksort and selection sort do not have this property; quicksort's best case is θ(n log n), and selection sort always runs in θ(n^2) regardless of the initial order of the data.

Which of the Sorts in the Textbook Can Be Characterized