Question 14180 – NIC-NIELIT STA 2020
December 1, 2023Question 14185 – NIC-NIELIT STA 2020
December 1, 2023Question 14184 – NIC-NIELIT STA 2020
Which of the following is the correct recurrence for the worst case of QuickSort?
Correct Answer: B
Question 109 Explanation:
T(n) = T(n-1) + n
T(n-1) = (n-1) + T(n-2)
T(n-2) = (n-2) + T(n-3)
…
T(3) = T(2) + 3
T(2) = T(1) + 2
T(1) = 0
Hence,
T(n) = n + (n-1) + (n-2) … + 3 + 2
=n2 /2
=O(n2)
T(n-1) = (n-1) + T(n-2)
T(n-2) = (n-2) + T(n-3)
…
T(3) = T(2) + 3
T(2) = T(1) + 2
T(1) = 0
Hence,
T(n) = n + (n-1) + (n-2) … + 3 + 2
=n2 /2
=O(n2)
T(n) = T(n – 4) + T(n – 2) + O(1)
T(n) = T(n – 1) + T(0) + O(n)
T(n) = 2T(n/2) + O(n)
T(n) = 4T(n/2) + O(n)