The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
973 views

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?

  1. $t_{1} = t_{2}$
  2. $t_{1} > t_{2}$
  3. $t_{1} < t_{2}$
  4. $t_{1}=t_{2}+5 \log 5$
asked in Algorithms by Veteran (43.4k points)
edited by | 973 views
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
@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?
the example you have taken it doesnt require to include the swaps i think
Has anybody got the correct answer and explaination yet?? And no, I think question is framed correctly.
how to deal with this kind of question which does not consider any pivot element ??
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})$.

5 Answers

+13 votes
Best answer
ACTUALLY IN BOTH THE CASES IT WILL TAKE $O(n^2)$ TIME ($O(n)$ TIME FOR PARTITION ALGORITHM AND $T(n-1)$ TIME FOR SUB PROBLEM. AS $n$ IS THE NUMBER OF INPUTS AND IN THE 2ND CASE INPUTS ARE 5(GREATER THAN 1ST ONE THAT IS 4) I THINK $t_1<t_2$
answered by Active (2k points)
edited by
@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.
+4 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.

answered by Loyal (3.1k points)
+1 vote
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).
answered by Active (1.4k points)
0 votes
The question seems to be wrong.There should be 5 inputs for the 1st case.otherwise t1<t2
answered by Active (2k points)
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.
0 votes
They said that time taken by input 1 and 2 are t1 and t2 not time complexity. So we consider value here.
answered by (37 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,997 questions
37,681 answers
96,746 comments
35,329 users