recategorized by
14,928 views
45 votes
45 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 $\left[1 \ 2 \ 3 \ 4\right]$ and $\left[5 \ 4 \ 3 \ 2 \ 1\right]$, 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$ 
recategorized by

5 Answers

Best answer
56 votes
56 votes
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.
edited by
15 votes
15 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
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 votes
–1 votes
The question seems to be wrong.There should be 5 inputs for the 1st case.otherwise t1<t2
Answer:

Related questions

2 votes
2 votes
2 answers
1
Bikram asked Oct 4, 2016
764 views
About how many compares will Quicksort() make when sorting an array of N items that are all equal?$\Theta(\lg N)$$\Theta(N\lg N)$$\Theta(\lg \lg N)$$\Theta(N/\lg N)$
24 votes
24 votes
4 answers
3
makhdoom ghaya asked Nov 14, 2016
5,181 views
Solve the recurrence equations:$T(n) = T(n - 1)+ n$$T(1) = 1$