@4:09 if you haven't done this analysis, it's very fun. Try 3, 7, and 9! Thanks for digressing 😃 I always had this question but never tried it myself before it was mentioned here.
Hi MIT thanks for all the quality videos you are making, it really helps a lot! I was just wondering is there R3 video? Because I cannot seem to find it, neither here nor on the website.
Pretty late response but i was wondering the same thing so thought I'd answer anyway. No R3 video seems to be available, but notes are still up for grabs! ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation3.pdf
Every number has a 1/n probability. The summation goes from 1 to N. However, the probabilities of the left half and the right half are symmetric, so its simplified such that the summation goes up ceil(N/2) and each weight is doubled, hence 2/n.
why does the summation of j from ceiling(n/2)-1 to n-1 equal n^2 times a constant??? Is it because we're replacing the summation with the closed form of the summation?
Summation of [(n/2)-1, n-1] is the same as subtracting the summation of [1, n/2] from the summation of [1, n-1]. Sum(1,x) is (1/2)(x)(x+1) or roughly (1/2)x^2. The right side of the equation is then, roughly, (1/2) n^2 - (1/2)(n/2)^2. There might be some off by one errors, but the goal is only to demonstrate that expectation
3 years later might be a stretch but will leave this comment here incase someone else wonders this , the term did not disappear , we choose the MAX of both terms , so while analysing for j = 1 to n , we take ET(n-j) till j = n/2 and ET(j-1) after, so adding them all up we get the equivalent of 2 * (summation from j=n/2 to n of ET(j-1))
@4:09 if you haven't done this analysis, it's very fun. Try 3, 7, and 9! Thanks for digressing 😃 I always had this question but never tried it myself before it was mentioned here.
@2:44 start
The hero we need but don't deserve
Tough crowd.
> I'm making lots of mistakes, buts its good to catch your attention.
No its not.
lmao full of NPC's
Best video on randomized quick sort
Hi MIT thanks for all the quality videos you are making, it really helps a lot! I was just wondering is there R3 video? Because I cannot seem to find it, neither here nor on the website.
Pretty late response but i was wondering the same thing so thought I'd answer anyway. No R3 video seems to be available, but notes are still up for grabs!
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation3.pdf
how did he get 2/n as the probability of picking a number? He said that numbers are repeated, can anyone explain this?
Every number has a 1/n probability. The summation goes from 1 to N. However, the probabilities of the left half and the right half are symmetric, so its simplified such that the summation goes up ceil(N/2) and each weight is doubled, hence 2/n.
why does the summation of j from ceiling(n/2)-1 to n-1 equal n^2 times a constant???
Is it because we're replacing the summation with the closed form of the summation?
Summation of [(n/2)-1, n-1] is the same as subtracting the summation of [1, n/2] from the summation of [1, n-1]. Sum(1,x) is (1/2)(x)(x+1) or roughly (1/2)x^2. The right side of the equation is then, roughly, (1/2) n^2 - (1/2)(n/2)^2. There might be some off by one errors, but the goal is only to demonstrate that expectation
For randomized quicksort @22:54 what happened to ET(n-j), why is it only ET(j-1)?
3 years later might be a stretch but will leave this comment here incase someone else wonders this ,
the term did not disappear , we choose the MAX of both terms , so while analysing for j = 1 to n , we take ET(n-j) till j = n/2 and ET(j-1) after, so adding them all up we get the equivalent of 2 * (summation from j=n/2 to n of ET(j-1))
@13:41 seems missing the probability Pr(j) term
He corrected it later 20:00
Thank you very much
Saved me just on time