ISRO-DEC2017-48

Question

Quick-sort is run on $2$ inputs shown below to sort in ascending order :

• A. $1,2,3\ldots n$
• B. $n,n-1,n-2\ldots 1$

Let $C$1 and $C2$ be the number of comparisons made for A and B respectively. Then, 

• A. $C1>C2$
• B. $C1=C2$
• C. $C1<C2$
• D. Cannot say anything for arbitrary $n$

Comments

They haven't said anything about the pivot. Only if in both the cases the greatest or the smallest element is chosen, worst case occurs. Else can't say anything about the number of comparisons.

Answer 1

option b as both are worst case in the case of quick sort.

Comments

Worst case occurs only when the greatest or the smallest element is chosen as the pivot.

So traditionally when the last element is chosen as pivot (where elements are in ascending order or descending), it turns out to be the largest or the smallest element.

But they haven't said anything about the pivot. If you give random pivot for both, the number of comparisons may not be the same.

---

even if you give random, it may be the case the random element selected is largest or the smallest, so the number of comparisons may reach upto n^2.

---

yes ..."may be the case" .. not "will be the case"

---

if you take the upper bound , which is the usual way it will be option b only.

---

upper bound? Number of comparison is different from time complexity. Number of comparison is "countable"

---

ISRO answer key says option (A)

---

upper bound in the sense of worst case.

---

ISRO corrected this in revised key,

Answer is B

---

@Shiva, can u plz provide me a link to this Question paper revised answer keys??

---

https://gateoverflow.in/2744/gate1996-2-15