GATE CSE 1987 | Question: 1-xviii

Question

Let $P$ be a quicksort program to sort numbers in ascending order. Let $t_{1}$ and $t_{2}$ be the time taken by the program for the inputs $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$, respectively. Which of the following holds?

• A. $t_{1} = t_{2}$
• B. $t_{1} > t_{2}$
• C. $t_{1} < t_{2}$
• D. $t_{1}=t_{2}+5 \log 5$ 

Comments

The number of inputs is different in both cases. ([1,2,3,4] compared to [5,4,3,2,1]). The only interesting thing about the question is to observe the fact that both represent the worst case sorting times of quicksort (without randomised pivot) resulting from the recurrence:  $T(n) = T(n-1) + \Theta(n) = \Theta(n^{2})$.

---

https://gateoverflow.in/581/gate1992-03-iv

---

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

Answer 1

Actually, in both the cases, it will take $O(n^{2})$ time for partition algorithm and $T(n-1)$ time for subproblem. As $n$ is the number of inputs and in the $2^{\text{nd}}$ case inputs are $5($greater than $1^{\text{st}}$ one that is $4),t_{1}<t_{2}.$

Correct Answer: C.

Comments

@arjun sir , How can you certian about the answer because they didn't mention the position of pivot here .

---

How to solve this when no pivott is given.. answer should be a?

---

answer C) is correct..time taken is asked not the time complexity and by default we should consider last element as pivot.

---

yes,if it ask about time complexity, then t1=t2 will be ans

---

Yes.......

---

@reena , I don't think that there is any rule that by default we should have to pick last element as pivot. If possible please provide any good reference for it.

---

@ankitgupta.1729

it is true partitioning will vary acc to implementation, how we select pivot element but if you consider CLRS (gate also based on STD. books ) then for one algorithm both are worst case scenario that are given to us, one is lesser than another one then we have to go with third one , eventually they talked about time not time complexity i.e. option C)

correct me if I'm wrong ? 

---

@Aks9639

yeah agree

---

@Rohan Ghosh,

Because of such a small value of n in both the cases, why we are not considering the time taken to be O(1).

If so then A should be the correct answer. Please suggest.

---

@srestha maam @arjun sir can you please tell how t1=t2 when complexity is asked? I am unable to recollect. Is it so that their size is fixed(5 and 4) which are constant values hence complexity will be O(1)?

---

@ankit3009  I understood the answer but like size of the arrays are constant so (A) seems more logical if I was in exam. What you think?

---

@adad20

We generally opt for the best case as default. If (time complexity + N length) would have been the case then we would be thinking about positioning the pivot element, but here they have asked for (time required + constant length) array. As time is asked over the constant length and both arrays are worst cases of Quick Sort algorithm, so (C) seems correct to me, only because the length of t2 is greater than the length of t1, if they would have been of same size then (A) would be chosen. 

If it would have been time complexity then option A would be chosen as both are worst cases and constant length array is given of which TC would be O(1).

---

If P2  were [4321] then ans would be t1<t2 ?(as in Quicksort worst and average case having different time complexity)

---

Running time of an algorithm depends on various factors such as processor speed etc.

So it cannot be definitely said.. Whether t1<t2 as both P1[1234] and P2[4321] are worst cases for quick sort

Check the best answer in this question: https://gateoverflow.in/8480/gate-cse-2015-set-3-question-27

---

Understood . Thankyou @Shubhodeep

Answer 2

In this questions ,they have asked the running time and not number of comparisons or swaps.

Time complexity with depend on n.

Since ,both the inputs [1,2,3,4] and [5,4,3,2,1] are already sorted, so both take O(n^2) time.

(a) is correct.

Comments

bt Here # of elements r 4 and 5 .... So option C ....

---

yes,if it ask about time complexity, then t1=t2 is correct but here they have asked about time taken to compare so c will be the ans.

---

you're right @Abhishek Gupta 1

---

The time complexity and running time are two different things altogether.Time complexity is a complete theoretical concept related to algorithms, while running time is the time a code would take to run, not at all theoretical. Two algorithms may have the same time complexity, say O(n²), but one may take twice as much running time as the other one.

time taken by program ≠ time complexity of program

time taken by program = run time of a program

Stackoverflow link

Answer 3

It will be option A.t1 = t2 ,if the list is already sorted in ascending,descending or even all elements in the list are same (all elements identical) it will be have worst case partion for quicksort and complexity will be O(n^2).

Comments

The time complexity is going to be same, but not the running time due to the size of inputs.

Answer 4

The question seems to be wrong.There should be 5 inputs for the 1st case.otherwise t1<t2

Comments

t1=t2 .In both cases if last element is taken as pivot then n-1element in the lower part and 1 element in the right half part..this thing repeat again.so worst happen when i/p is already sorted even in ascending order or in descending order.