But for 1,2,3,4 i think there will be no swaps because they are already in place we only need to compare only

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+20 votes

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 $[1 \ 2 \ 3 \ 4]$ and $[5 \ 4 \ 3 \ 2 \ 1]$, respectively. Which of the following holds?

- $t_{1} = t_{2}$
- $t_{1} > t_{2}$
- $t_{1} < t_{2}$
- $t_{1}=t_{2}+5 \log 5$

–1

But for 1,2,3,4 i think there will be no swaps because they are already in place we only need to compare only

+1

@Bhagirathi, yes it is sorted, and it is the worst case for quicksort, now if you want to do time estimation then you have to consider the implementation also....right?

0

Has anybody got the correct answer and explaination yet?? And no, I think question is framed correctly.

+3

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})$.

+19 votes

Best answer

+8 votes

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.

+4 votes

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).

–1 vote

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,716 questions

46,751 answers

140,562 comments

58,405 users