COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
O(1)
|
|
|
O(nlogn)
|
|
|
O(n)
|
|
|
O(n^2)
|
Detailed explanation-1: -In Quick sort, if the array is already sorted whether in decreasing or in non-decreasing order, then it takes O(n2) time. Merge sort gives time complexity of O(nlogn) in every case, be it best, average or worst. In merge sort, performance is affected least by the order of input sequence.
Detailed explanation-2: -Given an input of an array already sorted, merge sort would still need to go through the same sorting process as for any other array. As a result, even for a sorted array, the running time would still be O(n log n) .
Detailed explanation-3: -Time Complexity If the array is already sorted, then the algorithm picks the first element from the unsorted subarray and puts it at the end of the sorted subarray. So the time complexity for the sorted array is O(n).
Detailed explanation-4: -Runtime Difference Sorted / Unsorted Elements Merge Sort is about three times faster for pre-sorted elements than for unsorted elements. However, the number of comparison operations differs by only about one third.
Detailed explanation-5: -Merge sort is based on the divide and conquer approach. Therefore, the time complexity of Merge Sort is (nlogn).