COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Recurrence is T(n) = T(n-2) + O(n) and time complexity is O(n^2)
|
|
|
Recurrence is T(n) = T(n-1) + O(n) and time complexity is O(n^2)
|
|
|
Recurrence is T(n) = 2T(n/2) + O(n) and time complexity is O(nLogn)
|
|
|
Recurrence is T(n) = T(n/10) + T(9n/10) + O(n) and time complexity is O(nLogn)
|
Detailed explanation-1: -Detailed Solution Quicksort: In Quicksort, the worst-case takes (n2) time. The worst case of quicksort is when the first or the last element is chosen as the pivot element.
Detailed explanation-2: -Recurrence relation of the quick sort: T(n) = c, if n = 1. T(n) = T(i) + T(n-i-1) + cn, if n > 1.
Detailed explanation-3: -The worst-case time complexity of a typical implementation of QuickSort is O(n2). The worst case occurs when the picked pivot is always an extreme (smallest or largest) element. This happens when the input array is sorted or reverses sorted and either the first or last element is picked as a pivot.
Detailed explanation-4: -Worst case occurs when the subarrays are completely unbalanced. There is 1 element in one subarray and (n-1) elements in the other subarray.