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? $t_{1} = t_{2}$ $t_{1} > t_{2}$ $t_{1} < t_{2}$ $t_{1}=t_{2}+5 \log 5$ Algorithms gate1987 algorithms sorting quick-sort + – makhdoom ghaya asked Nov 8, 2016 • recategorized Apr 22, 2021 by Lakshman Bhaiya makhdoom ghaya 15.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments krish__ commented Nov 3, 2017 reply Follow Share 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 votes 5 votes Rishi yadav commented Jul 31, 2019 reply Follow Share https://gateoverflow.in/581/gate1992-03-iv 0 votes 0 votes Rishi yadav commented Dec 31, 2019 reply Follow Share https://gateoverflow.in/2744/gate1996-2-15 0 votes 0 votes Please log in or register to add a comment.
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. Rohan Ghosh answered Jun 25, 2015 • edited Apr 15, 2021 by Lakshman Bhaiya Rohan Ghosh comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments Shivani Shukla commented Nov 2, 2022 reply Follow Share If P2 were [4321] then ans would be t1<t2 ?(as in Quicksort worst and average case having different time complexity) 0 votes 0 votes Shubhodeep commented Nov 6, 2022 reply Follow Share 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 1 votes 1 votes Shivani Shukla commented Nov 7, 2022 reply Follow Share Understood . Thankyou @Shubhodeep 1 votes 1 votes Please log in or register to add a comment.
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. gshivam63 answered Jun 4, 2016 gshivam63 comment Share Follow See all 4 Comments See all 4 4 Comments reply Puja Mishra commented Jan 9, 2018 reply Follow Share bt Here # of elements r 4 and 5 .... So option C .... 0 votes 0 votes Abhishek Gupta 1 commented Nov 28, 2018 reply Follow Share 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. 4 votes 4 votes Manu Shaurya commented May 7, 2019 reply Follow Share you're right @Abhishek Gupta 1 1 votes 1 votes Ritik gupta commented May 3, 2021 i edited by Ritik gupta May 4, 2021 reply Follow Share 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 1 votes 1 votes Please log in or register to add a comment.
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). Surajit answered Dec 20, 2016 Surajit comment Share Follow See 1 comment See all 1 1 comment reply Manu Shaurya commented May 7, 2019 reply Follow Share The time complexity is going to be same, but not the running time due to the size of inputs. 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes The question seems to be wrong.There should be 5 inputs for the 1st case.otherwise t1<t2 Rohan Ghosh answered Jun 27, 2015 Rohan Ghosh comment Share Follow See 1 comment See all 1 1 comment reply BILLY commented Dec 25, 2016 reply Follow Share 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 0 votes Please log in or register to add a comment.