QuickSort
Question 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.
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

Question 1 Explanation:
When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty subblock, one element (pivot) in the correct place and sub block of size n1.
Hence recurrence relation T(n) = T(n  1) + T(1) + cn.
Hence recurrence relation T(n) = T(n  1) + T(1) + cn.
Question 2 
Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t_{1} and t_{2} be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
t_{1}=5  
t_{1}  
t_{1}>t_{2}  
t_{1}=t_{2} 
Question 2 Explanation:
[1, 2, 3, 4, 5] [4, 1, 5, 3, 2]
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2^{nd} array through not in sorted manner.
Hence t_{1}> t_{2}.
Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2^{nd} array through not in sorted manner.
Hence t_{1}> t_{2}.
Question 3 
Which of the following algorithm design techniques is used in the quicksort algorithm?
Dynamic programming  
Backtracking  
Divide and conquer  
Greedy method 
Question 3 Explanation:
In quick sort, we use divide and conquer technique.
Question 4 
Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.
O(n^2) 
Question 4 Explanation:
For n distinct elements the algorithm will take maximum time when:
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
→ The array is already sorted in ascending order.
→ The array is already sorted in descending order.
There are 4 questions to complete.