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

@Ujjwal_Nikam can we say that t1<t2 because t2 has more swaps than t1?

---

@Rishabh1006 Yes,bcz reverse-sorted i/p causes more swaps and deeper partitioning than sorted i/p in quicksort.

---

https://gateoverflow.in/2744/gate-cse-1996-question-2-15 similar question

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

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

---

yes i also thought the same

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

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

---

if t1=1, 2,3,4 t2=4, 3,2,1 both t1, t2 takes same time

Since t2 has more inputs than t1, so, t2 takes more comparisons than t1. So, option C is correct

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

In the ascending order thing we don't have to swap any element and we just have to compare with the remaining elements.

Where as in descending order things we have to compare as well as SWAP  the element.

The time complexity of both the algorithm will be O(n2)but the time taken for descending order will be greater than the time taken for the ascending order.

Answer 5

They said that time taken by input 1 and 2 are t1 and t2 not time complexity. So we consider value here.

Comments

Time complexicity in both the case will be equal, because both will take worst time to compute ie O(n^2).

Answer 6

in this question they have asked about time taken not time complexity . they wanted to compare time exact time consumed between t1 and t2 inputs .

even . if we take a pivot which yeald you to O(nlogn) at best take .

the comparison would be :

k*(4*log(4)) time for t1 input < k*(5*log(5)) time for t2 input . k depends on system on which algorithm is runned and also on specific steps and comparisons . since we are running on the same quicksort algorithm . it maximum depend on system .
 

now let compare for worst case . it will happen when pivot is placed in last position everytime :

T(n) = t(n-1)+n = O(n^2).

on comparing time consumed on worst case :

k*(4^2) < k*(5^2) , k depends on system on which algorithm is runned and also on specific steps and comparisons . since we are running on the same quicksort algorithm . it maximum depend on system .

in both cases t2>t1 . therefore answer is Option C .