Question 10146 – Time-Complexity

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1,2,3,...,n
(ii) n,n-1,n-2,...,2,1

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

Correct Answer: C

Question 5 Explanation:

Both are the worst cases of Quick sort, i.e., either the elements are already in increasing order or the elements are already in decreasing order.
So, option is (C) is correct.

C₁ < C₂

C₁ > C₂

C₁ = C₂

we cannot say anything for arbitrary n.

0 0 votes

Article Rating

0 Comments

Inline Feedbacks

View all comments