NIELIT 2016 MAR Scientist B - Section C: 12

Question

Which of the following sorting algorithms does not have a worst case running time of $O(n​^2​)$?

• A. Insertion sort.
• B. Merge sort.
• C. Quick sort.
• D. Bubble sort.

Comments

Merge sort.

Answer 1

for every case Merge Sort give TC = O ( n logn ) 

and nlogn < n^2 , so merge sort takes less than n^2.

Answer 2

Worst case time of insertion sort is O(n^2) when array is in decreasing order like 9, 8 , 7 ,6

Worst case time of merge sort is O(n*logn) . Time complexity of merge sort is always n*logn whether it is worst case , best case or average case

Worst case time of bubble sort is O(n*n) when array is in decreasing order

Worst case  time of quick sort is O(n^2) . quick sort gives worst case time when it is in ascending order or descending order or when all elements of an array are same.

Answer 3

Merge sort- nlogn all cases

Answer 4

Merge sort.

You may think of quick sort also,but worst case time complexity of quick sort is O(n^2) in the case when the array is already sorted either in ascending or descending order.