ALGORITHM
Answers
-4
Kashif Ahmed Shariff Posted on Sep 12, 2019 08:00 PM
I read this long back I think c option is correct i.e. O(n^2) since randomized quick sort would work same as quick sort in case like if all the elements in the list are same. e.g. 3,3,3,3,3,,3. And sometimes the random element selected would lead to division such that we divide the array into (1,n-1). I hope I'm correct please correct me if you have some valid points.
4
Arnab Das Posted on Sep 12, 2019 08:27 PM
Option (C) Even if we pick randomly still there is a chance to pick the smallest or largest element everytime as a pivot (though that probablity is very less). so worst case still remain O(n^2).
3
Nabati Basu Posted on Sep 12, 2019 11:50 PM
It is O(n^2) Because we can have an input like 3,3,3,3,3,3 and any number chosen in random will be always 3.
-1
Anupam biswas Posted on Sep 13, 2019 04:15 PM
C N2 here we are randomly taking the pivot element.. Say if the given array is in increasing or decreasing order and if we randomly select the pivot and each time we select the first element as pivort it an exam or worst case it give N2 time complicity... T(n) = t(n-1)+n
0
Alok Tripathi Posted on Sep 14, 2019 02:13 AM
Since worst case is asked and also the picking up is random the time complexity would be 0(n^2) case in which all elements are same or division is(1,n-1).
0
ROHAN VERMA Posted on Sep 14, 2019 04:39 PM
c
0
Shourya Srivastava Posted on Apr 29, 2020 07:11 AM
O(n^2) because of this case [2,2,2,2,2,2] same elements are there in the array
0
Jamyang Lotus Posted on Jul 02, 2020 02:10 PM
Worst case time complexity of Randomized quicksort is O(n^2) because the only difference in randomized quicksort from standard quicksort is the way of chosing the pivot element. According to probabilistic analysis by chosing pivot randomly there is a very less chance of partitioning the array (n-1),1 part,So, in the worst case there is a chance that T(n) = T(n-1) + 1.
