A&DS S01E03. Quick sort. Order statistics

0:00 [Music] so this is the third lecture of our course today we'll talk about one more sourcing algorithm we'll talk about quicksort algorithm and quicksort algorithm is a little bit different from what we learned on the first lecture it's different because it is randomized so first we will talk about what is the randomized algorithm and how to measure the randomized

0:52 so what is the randomized algorithm what usually happens usually you have some algorithm like we did in the first lecture it has some input data and some output data so you have some input here like for sorting algorithm you have some array for input and some output again in certain algorithm you are you input the array and you output the same array in the soft order uh what happens when you have a randomized algorithm you have another source of input so you have another input here and that input gives you some random

1:38 numbers i don't know why it's not working for you that's sad maybe you have some problem with twitch i don't know which is strange okay you can watch it in the recorded version but it said you can't watch live okay so you have some input data some output data and additional input source of input which

2:26 gives viewers some random numbers and the interesting thing is that random data may help you to solve the problem faster so sometimes happen that these random numbers can help you to solve the problem ah for example so we will learn the first randomized algorithm it is quicksort algorithm so how the quick sort algorithm works maybe you have some array so we have some array a and we want to sort this array in increasing order so what we can do we will do the following we will pick the random element of this array let's

3:11 pick some element x it's it's random and then we'll split the array into parts left part and right in the left part we will put all elements which are less than x so we put all elements less than x and therefore and in the right part we'll put all elements which are bigger than n so let's create a it's like graph or equal to x

3:58 x um let's see i claimed that we can split array into two parts in linear time so how to split array a into parts in linear time we simply go from left to right and just look on each element we take this element see if this element is less than x we put it in in the left part if it is greater or equal than x we put it in the right part so in linear time we will get these two arrays cool now what we can do we can call the same algorithm recursively for these both parts so we

4:43 call it again for this part again we pick some random element split into two parts again pick some random elements split it into parts and so on until we have a array of size one when we have a size one it's already sorted that's all that that that's how the quick sort algorithms work uh should we write the code no let's write the code it will be simple ah let's first let's let's upgrade it a little bit instead of having uh new errors each time we can upgrade it by using the same array for these two halves so instead of splitting array into two

5:30 arrays we will use the same array but just split it in between so we'll we'll use the same array a just put the elements less than x in the left half of this array and elements greater or equal to x in the right part of this ring and then call the same procedure for these both parts if we yes we pick elements framework so sometimes we we can pick the bad element so this element is not always a good element so

6:17 in this picture we split array almost in half but in reality you may pick some wrong elements so the array will be split it not in equal parts so it may happen it's yes it's it's more like merge sort but in merge sort we first split array then merge them together and here we just split erase and then uh in two halves which are first elements are less than second elements and then called the recursive positions like uh merge procedure in reverse so in in merge sort we first split array call recursive calls and then merge this to a recent one and here we just speak the element split arrays in in split area in two parts and then

7:04 call the cursor procedure for this part yes we can pick the same element several times that's fine yes we'll discuss why why is drop why is it first we will discuss a little bit uh later so let's let's just write the code first first i like to write the code ah so every time you call the recursive procedure so every time you give the recursive procedure some segment of the array so the segment is defined by its borders so we'll have left borders l and right borders are so we need to sort all elements from l

7:49 to r minus one nice let's go so first if the size of this part is less oracle than one so if r minus l is less or equal than the one then we have either empty array or array of size one so it's already sorted so we just do that if the size of ray is at least 2 then we pick the random element

8:51 asks about home tasks you can ask in comments on on code forces i think it's better to discuss it then but you can ask it now maybe someone will answer it cool so we pick the random element and now we need to split array into two parts so how can we do it we'll go from left to right and maintain the following property we go from left to right and each time we'll split this prefix into two parts so these elements will be less than x and these elements would be greater than x

9:38 so this will be from l to m and this is r this is i so go from left to right in this variable i take next element this element if this element is greater than or equal to x then it stays in place if it is less than x then we will split this element to this element and increase the variable m let's say we go from so let's say m equals to l then go for

10:25 i from l to r minus one take next element see if this element is less than x then we move this element to position m right so we smoke that's all split in procedure go from left to right take the element put it here so in the end we will have the array split it into the path so we have these elements less than x these

11:11 elements create article on x this is l this is m this is r and now we simply call the same procedure twice so we call sort from l to m and sort from envelope that's basically all implementation of the quicksort it's not the best implementation now we'll discuss why it's not the best implementation but it's good enough now did anyone find

11:59 did did anyone find something strange about this procedure this procedure sometimes doesn't work so sometimes for some race we have very strange situations can you find out what this is for some instructions why isn't it suitable hmm it's not snap it's fall

12:47 yes the biggest problem of this implementation is because because is that it is doesn't work when you have equal elements so if you have several equal elements in the array simply swaps two elements we take elements a i and elements am and we just swap these two elements these elements go here can i illustrate that okay let's let's illustrate an example so let's let's have summary

13:34 let's say three five two six four and let's say x equal to i don't know five so what happens we have l l here m here and r here now we go from left to right each time we take element if it is less than x then we swap it into position m so now m equal to l so it stays in place so this element is less than x now we move to the next element see if this element is not less than x so it stays on in the same place so this element is greater than the complex

14:22 and m is here now we take the next element see this element is less than x so we swap this element to the last element here so let's swap these two elements two is here five is here now we have two elements these two elements are less than x and this element is greater equal to x and m is moved to the right and so on we take take the next element see if this element is greater or equal to x then it stays in the same place so these elements are greater than 4x now we take next element if it is less than x and they swap it with position m so we swap these two elements 4 goes

15:08 here 5 goes here move m to the right and now in the end we have these three elements less than x and these two elements greater equals no i will not have swims in spanish sorry it actually will be cool to learn spanish i think but not this year this year was recording streams in english maybe later

15:53 cool so again what is the problem the problem is when you have several elements of the problem is when you have several equal elements so so if you end up in the wrong situation so we have l here r here so you pick a random element so all elements are equal so you pick x equal to now you try to split arrays into parts elements less than two and l is greater than two so you have no elements less than two so you have empty set of elements less than x and all elements greater equal inputs

16:39 you call the same procedure you have the same array so each time you have the same array you cannot split these elements into two groups because they are all equal so how can we improve this procedure how can we uh improve it to to be able to solve problems like this when we have equal elements just check if it's actually yeah this one solution you can check that all elements are equal but it's not not the best solution

17:27 because if all elements are equal but one is different like since you have many tools but one alarms okay there are different different ways how to solve this uh one of the simple way to solve this is to split array not in two parts but in three parts you can split array in three parts you can have elements less than x here are equal to x here and greater than x here so split right into three parts and then call the recursive procedure for this house so elements equal to x stays in place

18:14 so we only need to sort this two parts of the array okay that's one one of the way to solve this problem nice that's all that that that's how the quick start algorithm works now uh let's think about how to measure a stand complexity so on the first lecture we was talking about time complexity and we decided that we will only learn how to measure complexity in the worst case so each time when we calculate the

18:59 time capacity of the algorithm we will find the worst possible case and calculate the number of operations in the worst possible case so what is the worst possible case for this algorithm what can go wrong let's look at array a what element can we pick that will be the worst possible random element

19:45 a zero a zero may be good elements um yeah the problem is when you pick the element which is minimum possible or maximum possible so if you pick minimal possible element if each time you pick as x the minimal element so you split array like minimal element and all other elements then i can use minimal element and so on so every time you split the array into

20:31 like very unequal parts what will be the time complexity of this algorithm in this case yes today to today's only english lecture yeah time complexity will be n square again like we discussed on that in the first lecture here we spend end time let's put n minus 1 here and minus 2 here and so on so this total number of predictions will be big o of n square cool [Music] and actually this implementation may go even worse so in in this

21:17 implementation we may have even even more situation so what happened in this implementation if we pick a minimal element as x very strange thing so in this implementation if we pick minimal element as x we'll split the ring into two parts so we have elements less than x and greater or equal than x but x is the minimal element so we have empty array here and all elements in the right part so each time the size already is not decreasing so

22:03 each time you have array of size n so the total number of operations will be infinite so this procedure will infinitely call itself in a grassroot so the worst possible case may be infinite so sometimes this algorithm just doesn't finish is the problem it looks like a slightly uh major problem but actually it's not why it's not a big problem because we pick a random element and the probability that each time we'll pick the minimal element is very small actually it's infinitely small so if you uh pick

22:49 the first element on each iteration infinitely the probability of this situation is zero quick sort is actually pretty quick yes it's called quicksort because it's pretty quick comparing to merge sort and especially comparing the heap so we'll talk about this little bit a little bit later so uh in worst case this procedure may work infinitely and if you fix it like we did so if you pick the element equal to x here and greater than x here then time complexity in the worst case will be n square

23:34 nice so uh to measure the time complexity of the randomized algorithm we'll use slightly different technique because it's randomized so to measure the complexity of the randomized algorithm we will measure not the worst game type of complexity but the uh mathematical mean of the time capacitor will measure not the number of operations because number of operations is some random function so we'll call we'll calculate the estimated meaning of this random function so mean of the time of that number of operation which algorithm will take

24:24 [Music] and these mathematical averages calculate this one so it's just like let's say it's just sum of of x multiply the probability that time equal to x and it helps a lot because uh the probability that your algorithm looks very slow is very small so if you have n square iterations it means that each

25:10 time you pick the minimal element the probability that each time you will pick the minimal element is very small so the big biggest array the smallest probability so when we calculate when we multiply this big number of iterations by the small probability we'll get some something good cool [Music] now let's prove that for quick sort algorithm the mathematical average of the of it of of the time is actually n logan how can we prove this

26:02 let's see so we have array eight each time we pick some random element split array into two parts left one truly believe in this formula oh this is the standard formal form of mathematical formula i mean okay so let's calculate the mathematical average of this time complexity

26:49 we have some array we pick some random element uh so what we need to see uh the probability that they pick each element is uh so for each element x the probability that the peak element x is 1 divided by n right so let's see if we pick let's say k elements to the left part then time complexity will be so we split we need to split elements into two parts in linear time and then

27:34 we make two recursive calls here first recursive call is t of k and second recursive call is t of n minus k now this k is random so we can pick all elements with equal probability so to calculate the estimated value of t we actually need to find the sum of this multiplied by 1 over okay from 0 to n minus 1.

28:29 i just remove this stick so so every ray is an estimated period of the time now how can we solve this uh the easiest way to solve this is by doing the following let's say that if we pick element from this middle so if we pick one of the elements from this middle third of the element uh it is good so if we pick one of the elements in the middle of the array and over three elements here

29:15 then we make a good split so we'll split elements in not half but closed clock the sizes of both parts will be close to each other [Music] cool so what is the probability we will pick one element from from this group it is uh one over one third let's just remove this so we probably see one third we will pick one of the elements from this group if we pick one of the elements in this group then k will be from n over three to two and

30:02 over three so size of each of these parts will be no more than two-thirds of n uh so this sum will be no more let's see this normal uh then t of n over 3 plus t and 12. so this happens if you pick one of the elements from this middle group and if you pick one of the elements from this outer group you will split uh the array in some not not not very equal groups so if you pick one element here you will split every you will split your array very badly so

30:49 we will split it somehow like this we'll say this is the bad split so in the bad case which happens in two thirds of the case you will split something like that and we will say the worst possible case it when we split elements into groups like one and n minus one so we'll just it's no more then let's say t of n so this is the good split let's see this is the good split this is the bat split

31:35 i lost plus n plus so this happens when you pick one of the elements in the middle group and this happens when you pick one elements in in these groups so it happens with probabilities of one third this happens probability two first now let's just use this formula so what happens we move this to the left

32:20 so we had one over three here just remove this let's multiply everything by three so we have t of m no more than three n plus t of n over three plus t of two n over three something like this and now we just prove by induction that this actually is n log n let's prove let's prove that t of n is no more than c multiplied by n log

33:08 n it's like we did on the first lecture so we have n over 3 is smaller than 3 this is smaller than n so we use this formula for these two parts uh so we'll have something like t of n is no more than three m plus c n over three log n over three plus c 2 and number 3 [Music] and now just well like we did again like we did on the first lecture we use this logarithm c and logarithm of n over 3 is log n

33:56 minus log 3 here we have log n minus log three or two so in there we'll have something like this too too much mathematics for one lecture actually it will be the last formula in this lecture i promise so we have this ah let's just remove n from this so we have n multiplied by three plus here we have c n over three multiplied by log n so we have plus

34:46 log n plus all of us plus this c two and o three multiplied below again and then minus this and minus this uh minus uh c n over three multiplied by log no i removed n yes i moved n here so it's one here sorry ah minus c multiplied by log three right and minus c multiply two by three logarithm of three

35:37 yeah looks fine so now we simply move these two claws together so the sum of these thing is c multiplied by log n so we have this equal to c and log n plus something something like m like three minus this part three log three minus c two third log three and now we just pick the big value of c so we say if c is big enough so if c is big then this is less than zero

36:24 so this is less or equal than c log saying logan [Music] master theorem is you you can use something like master theorem because you have two two segments here so you have two recursive calls of different argument so master theorem is not very good for this okay it's good enough it's not seven we're very concerned so no no it's it's three three three three where do you see something it's two

37:10 and this is true my writing is not very good it's it's not it's it's not a big deal so you have some constants here so we have some constant here some constant value here so if c is big enough then this bracket is less than zero good another maybe a more natural way to think about this is like this so you may think about this algorithm like this so what actually happens let's see we have array a uh let's say if we take one of the

37:57 element from the middle group by random so we pick some random element maybe we'll pick a good element let's say if we pick element from this middle group it is a good way it is a good way this happens in every third case so every first every third time we pick element from array it belongs to this middle group let's say every uh peak we pick element from this group and when we pick element from from this middle group we'll split array into two parts and both parts

38:44 will have size no more than two-thirds of them so every third split uh will decrease the size of the array by at at least two thirds so the depth of the recursion will be again logarithmic so you have this big rate now after about three random picks you will split the race in into two pounds so each part will be at most two-thirds of end now again you make again here you may freeze you make three uh wrong picks and then you make a good peek

39:30 next again you take this part and again after about three peaks let's see you have some bad peaks and then you have good pick so big element from here you split element in and and so on so each time uh after some small number of peaks about three peaks you will have a good split so some some splits will be good and each blue split will decrease the size of ray by some constant factor so the depth of this recursion will be very it's actually the def this question will be about let's say three multiplied by logarithm off and base 3

40:16 something like that it's so that's more intuitive way to think about this and if the depth of recursion is logarithmic then the total time complexity will be n log n because on each layer of the recursion the total time complexity of all recursive calls will be n like in merge sort cool do we have enough time so let's talk about the following ah can we input what happens in practice so this quick sort is quick because it's relatively good in practice so what

41:01 might happen in practice in practice uh what happens you program the element sometimes you split elements you you split array in a good way sometimes you split right in the better way to increase the efficiency to increase this decrease this constant we can find the way to pick the better element we have better probability it's not it it will not be asymptotically better but it will decrease this constant factor in practice you not only think about the asymptotics but also also you think about the constant factor so you if you in practice you may want to decrease this quantum factor how can you do it uh you can pick the element uh in the middle with better probability

41:48 so how to pick elements from the middle group with bigger probability uh one of the way to do it is to pick not one element but let's say three elements let's pick three random elements from the array one element two element and three then look on these three elements and pick the middle one as x so we sort these three elements random elements and pick the middle one and if you pick three elements and take the median uh you'll have the better probability that this element will be closer to the center of the array

42:35 so and if this probability is bigger then this constant factor will be smaller so the total time complexity will be slightly smaller it will still be n log n but that this constant will be smaller alternatively you can pick not three elements but let's say five elements you can pick five elements and pick the middle one you will have slightly better performance and so on i think it's fine so so this is how how how you measure the time complexity of a randomized algorithm and how to measure time complexity of

43:20 the quick solver uh one of the one thing i want to notice is that we measure the time complexity in the worst case but this worst case is all over the inputs so we take the worst possible input let's say input is worst case but random is random so we take uh we take each input and calculate the time the average time complexity for this input and then takes the worst possible input so we take the input which have the

44:07 worst possible average time complexity so again we measure the time complexity in the worst case but the worst case is not all over these inputs not over this random values so random values are some random values and there is a better place can we use the gauss mobility you uh probably you can use gaussian probability because you you wanted probability over the sorted array but you didn't sort array so you have this array not in sort order but in some random order so you can't pick the middle element of gaussian probability basically you uh when when you give a summary all elements are equal for you you don't

44:54 know any relations between these two elements so it's strange to pick some non uh non-uniform distribution so if you pick elements of different probabilities in the worst case the the wrong element will be peaked to the bigger probability so the best thing you can do is just pick all elements with all with equal probabilities cool so let's move next next we'll move not to this sorting algorithm but we'll discuss something similar to the software algorithm we will discuss the order statistics problems

45:57 not sure about english so what is the problem clearly so have the following problem you're keeping some array and you need to find the element which will be a given index array and the index k you need to find the element of index k in the sorted array so if you sort this right

46:48 and pick the element index k that is that is the element you want to find so this is the case that is english is difficult i think it's all the statistics here fine good enough so you want to find this element in the tree good what is the obvious solution obvious solution is just to sort the array and then pick the element

47:33 that will cost you anytime just certain people ah and the interesting fact is that you can do it actually faster you can find the element with index k without sourcing the whole array so you can find this element and do not sort the color

48:23 [Music] now i will discuss the randomized algorithm which work faster than this at least time complexity the album works like this so we have the array a uh again like in quick sort algorithm let's pick some random element we pick some random element x pick this element x and split it into two parts so let's split it less than x and now let's look where is the element

49:09 of index k so if k is less than the size of the left part then we only need the leftovers so if k is here then we don't need these elements in the right part we only need these elements so we call the same recursive procedure but only for this left part of the array so again we'll take this now again we pick some random elements split it into two pulses see this and this see where where is element k pick pick this part again split it pick one part against plate pick one part and so on in the end we have only

49:54 one array one element in the in in this array that's a strange one for some reason twitch is not working for someone i don't know maybe i have some wrong settings let's i need to investigate this i don't know why that's all that that's how the algorithm works each time you pick the random element split right into parts then pick one of the parts which contains the element k and so on in the end you have uh the area of size one this small array contains this element

50:39 you won't find i should write the code let's write the code again let's have a recursive procedure let's say defined again we have elements from l to r yeah we need to find element k yes and we will maintain the invariant that k is between l and r so so k is greater

51:27 or equal to l and less than r now we see if this array have size one if r minus equal to one and then we return element if it is more than one we will split this array so we're saying x is the random element now again we do the same we make this split so we split elements from l to m r should i write it again okay let's do it again so we're gonna have m equal to l

52:13 for i from l to r minus one if element is less than x we swap and increase m so we split array into the parts less than x and greater points now we now we see which part contain element k so if k is less than m and then we make recursive call for the left part and if it's greater oracle equal to m then we make recursive call for this right part

53:13 that's all let's solve it out that's the whole algorithm what is the difference from the previous algorithm so it is it looks almost the same as the quick sort algorithm yeah so quick sort algorithm has time complexity and logan and i claim that this algorithm have better time complexity why it is different from the quick sorting game what is the key difference now this operation is almost so this part is actually equal to the same we have the same part in the quick start algorithm we just split array in two parts but it has one big difference from the quicksort algorithm

54:05 yeah the key difference is we make only one recursive call in quick sort we make two recursive calls we make recursive calls for left part and recursive calls together here we make only one recursive clause we go to the left part or to the right part so we have this recursive call or this recursive calls we never have these two recursive calls at the same time that's better so what will happen so y time complexity will be better so what happens we pick a random element and then pick one of the two halves so now again every third time we'll have good split and the good split will decrease the size of ray to like two thirds of n so we have total time complexity will be

54:52 n on the first iteration then we make a good split we have like two thirds of n then after another good split we have four ninths of n plus and so on and what is the sum of this uh huh series uh don't worry that's you know yeah yeah it's all the same so we have only one recursive call so each time we have no not not the sum of these recursive calls but only one recursive call and one recursive call costs you two thirds of n so this sum equals to 3m

55:40 so total time complexity will be linear that's all that's how you find the element in a solid order without sorting the whole array so you just split the array and then just remove one of the parts because you don't need to sort these elements and only make recursive call in one half and so on so the total time complexity will be linear that's all good any more questions by now yes i will upload it to youtube as always

56:29 okay and the final one and the final one final one uh one more algorithm uh what why do people use randomized algorithm there are many reasons uh first reasons is these algorithms sometimes are faster than uh the usual algorithms so for example this is quick sort i already erased this a quick sort algorithm is called quick because it's actually pretty quick comparing to for example heap sword because heaps are just pick random elements and quicksilver goes from left to right and splitting caching and so on i'll do it in a second so sometimes uh randomized logic will have

57:15 better asymptotics type complexity it happens for for some problems we know the first randomized algorithm but we don't know the first uh determined algorithm so sometimes scientists have found some good randomized algorithm but we didn't found the good determined algorithm that happens so the next will uh the final thing we will do in this lecture we will show how to achieve the same asymptotics using the determined algorithm without any randomization uh they asked me to repeat this let's repeat this once again so what happens here uh we split we pick the random element and split

58:02 array in two parts and the probability about one third we will split the array into parts essentially that both parts will have size at most two-thirds of n so the probability of this is about one-third so after you have the size decrease to the first of n again you will have some random peak and after some random peaks you will have four ninths of n and because you have only one recursive call here the total time complexity will be sum of this series so the sum of the series 3 is 3m so it's linear so it's just sum of some geometrical progression

58:51 it's actually this happens a lot in computer science you have some algorithms which decreases the size of input by some constant factor and the sum of all these recursive calls will be linear it's not this happens not not only in this algorithm it happens a lot actually when you have some linear algorithm which works like this you have some big input then you do some magic stuff and decrease the size of input by constant factor so the top end called the same the same algorithm for this smaller input so the total time complexity will be linear in this case good so okay again the final thing uh we will show how to achieve the same time complexity using determined algorithm

59:37 good let's just erase this what is the idea [Music] so why do we need randomization because we want to pick some good element x okay so the idea is already to pick some good element x and then split array into two parts and to pick the good element x we just pick the random element random element will be good with some good probability let's try to pick the good element the probability one just like find the determinant way to pick the good element uh yeah cool

1:00:25 uh this is the algorithm of five people listen up bloom floyd pride reviews so we need like five people to invent this algorithm cool how it works so what is the idea we do everything the same but they pick this element x not in random way but in determined way so we need to find the determinant way to find the good element x

1:01:10 somehow everything else will be the same so how to pick good element x you do it in the fun way you take the array a and you split it into groups of five elements so we have n over five groups two blocks uh let's draw it like this it's easier to show it so we have

1:02:00 so these are blocks so each block have size five and you have n over five blocks and more question this is already now what what what you can do you can find the medium element in each block so you take each block sort elements inside this block and take the median element so take this medium element this element is let's say greater than this element and smaller than this so this is the median element from these five elements okay

1:02:46 and you do it in each group so in each block you sort these five elements and take the middle one uh let's notice we can do this in linear time so we can in linear time we can split array into in the blocks and in linear time we can find the median in each group because the size of group is constant so you can just sort this element using any sorting algorithm and then take the middle element it will cost you some n multiplied by the size

1:03:33 of the block nice and then we'll do the following we'll take this median elements from each block and find this median of all mediums so take these elements and find the median of these elements again we have eight blocks let's let's get nine blues so if we have nine blocks we need to find this element and this element will be x

1:04:20 that's the whole outcome again what we do we take the array a split it into blocks of size five then find the median in each block and then find the median of these medians and say that this median of medians is x and now we do referencing that's all that's the whole algorithm yes that's that's a good question uh to find this median of medians we need to sort this uh elements but actually we don't need to sort them we only need to find the median and to find the median element

1:05:06 we can use the same algorithm recursively so what can we do first we spend some linear time to make all this just to find all these mediums and so on split everything uh now we take these median elements and call the same algorithm to find the median of all these medians so we'll spend t of n over 5 l time this is to find the medium no if we use quick sort here we'll spend

1:05:52 analog anytime we don't want to spend any login time yeah this is all people are very famous one again these all all these names may be familiar for you now we take we make the recursive call to find this median element and now we split array into two parts and make recursive call in the path which contain element a k so what may be the size of this thing what what maybe the maximal size of this group so make another recursive call of this

1:06:40 part which contains element k see for example we pick the left part so we pick the left part these are elements less than x what will be the maximal number of elements less than x in this array let's see where are the elements less than x so these elements are less than x and these elements are less than this elements and they are less than x so these elements are also less than x what other elements can be less than x actually

1:07:27 also these elements can be less than x because if we have x here here we have some elements less than x and here some elements more than this element so these elements also could be less than x so these elements also could be less than x and the same thing here so these are some elements which are less to some elements which are greater than x so these elements also can be less than x and this all all elements here cannot be less than x because these elements are greater than x and these elements in the bottom are greater than these elements so each element in this part of this

1:08:12 rectangle are greater than x so these are all the elements which could be possibly less than x what is the total number of these elements so we pick all elements here so over two here and like two of the five in each block here so we have let's see we have half of elements here and we have half of elements and from each block we have two of five elements so it's two of five elements okay let's see if we just this is this is n over five

1:08:58 plus n over two it's uh it's it's seven and so the maximal possible size of this part is seven and or ten that's all and now i plan this if you have this current formula then the time complexity is linear let's prove this [Music]

1:09:46 well again how to prove this uh we use mathematical induction i i promised it it was the last four moments but okay this is the last one so we want to prove that t of n is no more than c multiplied by n now we use this this use t of n is no more than n plus c n over five plus c seventeen over ten now we just said n here what we have here we have one plus c multiplied by n over five

1:10:31 plus zero and it's nine and ah don't know where you move to one and here right looks fine we use the same procedure for for every recursive call so every time on each recursive call we use this procedure we split the array into blocks find median find median of medians and so on this happens in each recursive call so so here we have the same recursive call and here we have the same degree circle and finally now what what we need to do

1:11:16 we need to find c such that this should be less or equal than than c multiplied by n so let's just divide it by n we have one plus and then of c not c just move this to the right we have c over 10 here multiply this by 10. so this is true then c is at least at at least 10. now we pick now we pick c equal to 10 and we have the correct proof and that's all again the algorithm is basically the same as the randomized one

1:12:03 the only difference is that we pick the element not in random fashion but in dismissive fashion so we will find the media and find the medium opinion and we claim that this element is the good divider so we pick this element x divide the array using this element x and then each half will be at most 7 n over 10 so total that complexity will be linear ah that's all okay i think it's all for today thank you for joining me today thank you for watching

1:12:53 [Music] do [Music] you