Question

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. Quick sort runs in Θ(n²) time 

II. Bubble sort runs in Θ(n²) time

III. Merge sort runs in Θ(n) time 

IV. Insertion sort runs in Θ(n) time 

(A) I and II only 

(B) I and III only 

(C) II and IV only 

(D) I and IV only

Answer 1

Correct option is (D) I and IV only

As input is already sorted quick sort runs in θ(n²) & insertion sort runs in θ(n).