Question

Consider the following statements
S1. In Quick sort, if array is sorted or almost sorted then quick sort algorithm gives worst case
complexity is O(n)
$2 in insertion sort, if array is sorted then insertion sort gives Best case complexity is O(n)
53. In insertion sort, if array is sorted then insertion sont gives worst case complexity is O(n)
Which of the above mentioned statements is true?​

Answer 1

Answer:

The answer is $2 in insertion sort, if array is sorted then insertion sort gives Best case complexity is O(n) 53.

Answer 2

The explanation for the given statements is as follows:

• Statement 1 - False: If the array is almost sorted or completely sorted in Quick sort then the worst-case complexity in the Quick sort algorithm is given by O( n² ).
• Statement 2 - True: If the array is sorted then the Best case complexity in Insertion sort is given by O( n ).
• Statement 3 - False:  If the array is sorted then the Worst-case complexity in Insertion sort is given by  O( n² ).

#SPJ2