Computer Sciences > GATE 2014 SET-3 > QuickSort
You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is
Correct : a
While choosing the central element often prevents the O(n2) case on already sorted data, a specific input sequence can still be constructed (an adversary array) that forces the central element to consistently be the smallest or largest in every sub-array.
This results in the most unbalanced partitions: one sub-array of size n-1 and one of size 0.
The recurrence relation for this worst case is:
T(n) = T(n-1) + O(n)
This solves to O(n2).
Similar Questions
A palindrome is a word that reads the same forwards and backwards. In a game
of words, a player has the following two plates painted with letters.
From...
Which number does not belong in the series below?
2, 5, 10, 17, 26, 37, 50, 64
Choose the word that is opposite in meaning to the word “coherent”.
Total Unique Visitors
Loading......