Randomized quick sort and amortized analysis | Quick Sort | Appliedcourse
HTML-код
- Опубликовано: 17 май 2019
- Chapter Name: Quick Sort
Please visit: gate.appliedroots.com/
For any queries you can either drop a mail to Gatecse@appliedroots.com or call us at +91 844-844-0102
Awesome video, keep it up..
Can you tell me what is the actual time complexity of RQsort? Just wonder cuz its N*logN in worst case but using probabilities and algebra you can show its on average far from N*logN. So do you know the exact number O(n)?
Thanks sir ji
Really nice video
Super helpful
This helped...!!
Very helpful 😊😊😊
good 1
What if the array has all of the same number?
It performs just like worst case
O(n2) complexity
worst case of the randomized quicksort should be O(n^2) isn't? Because In worst case anything can happen even if the probability of that event is very less. so getting smallest element each time as a random element is also possible. And any possible thing can happen in worst case. Please clarify Sir.
It is possible but what are chance of that? 9/9! If the array is 9 element long. Calculate the value, see how less it is.
he says that the probability of this is so close to zero so if your complexity in 98% of times is nlogn you wouldn't say that its n^2
To be very precise, the "expected" runtime of Randomized Quick sort is O(n lgn). We actually compute the expected runtime using expectations in probability theory. The absolute worst case is O(n^2), but the probability of that happening is too low. For most randomzied algorihtms, what we care about is the expected time and the probaility for the worst case happening. Randomization is a super powerful startegy in the deisgn of algorithms as we can give probabilites of the worst case happening which is often very very low. In the case of Randommized-Quick-Sort, the probability of picking the smallest element everytime resulting in the worst case of O(n^2) is 1/n*1/(n-1)*1/(n-2)*...*1 which is 1/(n!). Even for a small value of n=10, this probaility is 1/3628800 which is very small for all practical purposes. Yes, as you rightly pointed out this is still possible, but the chacne of that ahpenning is just too low that we can ignore it in practice. There is a whole subfield of algorithms called randomized algorithms, typically studied at graduate level, which focusses on solving hard algorithmic problems using randomization. Quicksort is one of the simplest randomzied algorihtms.
What if we end up getting the same number as pivot because of the randomised pivot, we will waste that pass unnecessarily comparing, since it is randomised so in order to get all the elements selected as a pivot will be more.
What I am trying to say here is if there are 10 elements. and we randomly select a pivot, after partitioning elements will be placed on its left and right, we can also happen to select the same pivot again and we will make unnecessary comparisons, of course, there would no swaps this time,
And another is if we want to get the array sorted by randomization we have to get all the elements selected as pivot only then the array would be sorted right, isn't that going to increase complexity.
I know practically it has been proven that the complexity is better, but my point is how can we leave something to randomization,
randomization also means selecting the same number again and again.
If you talk about randomization which will yield a better result, then all the numbers considered should not be part of the randomised function, this way every time different pivot would be selected and we will get the array sorted in one of the best ways.
Randomization is a super powerful startegy in the deisgn of algorithms as we can give probabilites of the worst case happening which is often very very low. In the case of Randommized-Quick-Sort, the probability of picking the smallest element everytime resulting in the worst case of O(n^2) is 1/n*1/(n-1)*1/(n-2)*...*1 which is 1/(n!). Even for a small value of n=10, this probaility is 1/3628800 which is very small for all practical purposes. Yes, as you rightly pointed out this is still possible, but the chacne of that ahpenning is just too low that we can ignore it in practice. There is a whole subfield of algorithms called randomized algorithms, typically studied at graduate level, which focusses on solving hard algorithmic problems using randomization. Quicksort is one of the simplest randomzied algorihtms
Kosom Israel
This video is totally WRONG! The worst case is O(n^2) and please don't hear him. It does not matter how improbable the worst case example is!