-4

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

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

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

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

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

c

0

O(n^2) because of this case [2,2,2,2,2,2] same elements are there in the array

0

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.

© 2020 - All rights are reserved- AAIC Technologies pvt ltd