Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting $n$ ($\geq 2$) numbers? In the recurrence equations given in the options below, $c$ is a constant.
In the worst case the pivot is the smallest or largest element, so partitioning costs $cn$ and leaves one subproblem of size $n-1$ and one of size 1. That gives $T(n) = T(n-1) + T(1) + cn$.
More Searching, Sorting and Hashing questions
GATE 2016 CS (CS1) Q23– The worst case running times of Insertion sort, Merge sort and Quick sort, respectively,…
GATE 2017 CS (CS1) Q58– Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of…
GATE 2014 CS (CS1) Q24– Quicksort P sorts ascending using the first element as pivot. Let t₁ and t₂ count its…
GATE 2014 CS (CS1) Q49– Find the minimum comparisons needed to find both minimum and maximum of 100 numbers.
GATE 2014 CS (CS3) Q24– Quicksort on n array elements always chooses the central array element as pivot. Find the…
GATE 2014 CS (CS3) Q52– listA contains n > 0 elements sorted in ascending order. Which statement about…