![Question 8171 – GATE 2015 [Set-1]](https://solutionsadda.in/wp-content/uploads/2019/05/green-new-logo.png){kind=logo}
ISRO CS 2009
January 4, 2024GATE 2014 [Set-1]
January 4, 2024Question 8171 – GATE 2015 [Set-1]
Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.
Correct Answer: B
Question 14 Explanation:
When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1.
Hence recurrence relation T(n) = T(n – 1) + T(1) + cn.
Hence recurrence relation T(n) = T(n – 1) + T(1) + cn.
T(n) = 2T(n/2) + cn
T(n) = T(n – 1) + T(1) + cn
T(n) = 2T(n – 1) + cn
T(n) = T(n/2) + cn
Subscribe
Login
0 Comments