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.2k 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.
–1 votes –1 votes They said that time taken by input 1 and 2 are t1 and t2 not time complexity. So we consider value here. vermamayank564 answered Aug 14, 2017 vermamayank564 comment Share Follow See 1 comment See all 1 1 comment reply sanjeet24 commented Jul 26, 2023 reply Follow Share Time complexicity in both the case will be equal, because both will take worst time to compute ie O(n^2). 0 votes 0 votes Please log in or register to add a comment.
