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

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.