Prev: Could another characterization of NPhard problems be that their naive algorithmic solution (e.g. permutations) is factorial; whereas, a dynamic programming algorithm is exponential?
Next: Sorry Tim, this is simply the most beautiful picture I have ever seen. It was worth it and I'd do it again.
From: Maciej Pilichowski on 5 May 2010 09:33 Hello, I am reading "Probability and Computing" by M.Mitzenmacher and E.Upfal [1]. I am having problems understanding how the probability of comparison of two elements is calculated. Input: the sorted list (y1,y2,...,yN) of numbers. We are looking for pivot element (chosen randomly). Question: what is probability that two elements yi and yj (j>i) will be compared? Answer (from book) [2]: yi and yj will be compared if either yi or yj will be selected as pivot in first draw from sequence (yi,yi+1,...,yj1,yj). So the probablity is: 2/(ji+1). The problem for me is the initial claim: for example, picking up yi in the first draw from the whole list will cause the comparison with yj (and viceversa) and the probability is 2/n. So, rather the "reverse" claim is true  none of the (yi+1,...,yj1) elements can be selected before yi or yj, but the "pool" size is not fixed (in first draw it is N for sure, but on the second it is smaller). Could someone please explain how the authors come up with such a simplified conclusion? Regards, [1] http://rads.stackoverflow.com/amzn/click/0521835402 [2] http://books.google.com/books?id=0bAYl6d7hvkC&lpg=PP1&dq=Probability%20and%20Computing&pg=PA37#v=onepage&q&f=false page 37  Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy. http://www.garaz.pol.pl/
From: Maciej Pilichowski on 17 May 2010 02:21 Solved: http://stackoverflow.com/questions/2750726/randomizedquicksortprobabilityoftwoelementscomparison  Moja wyprzedaz wszystkiego: ksiazki, plyty, filmy. http://www.garaz.pol.pl/

Pages: 1 Prev: Could another characterization of NPhard problems be that their naive algorithmic solution (e.g. permutations) is factorial; whereas, a dynamic programming algorithm is exponential? Next: Sorry Tim, this is simply the most beautiful picture I have ever seen. It was worth it and I'd do it again. 