1
$\begingroup$

I am having an issue in a specific part of the randomized quick-sort analysis.

As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random index, instead of just choosing a specific index each time.

Now suppose that we give an array of size say $n$ to our randomized quicksort algorithm.

enter image description here

enter image description here

Now I request to have a look at the proof of lemma-7.1 in the text given below. Now we have given an array to our algorithm which can be of any permutation of the elements, but in the paragraph just after the proof of $lemma-7.1$.

why is the author considering a sorted instance of our input array while doing the analysis?

Moreover if look at the text after equation $(7.2)$ where there have justified their logic of finding the probability that $z_i$ shall be compared with $z_j$ in our algorithm. Now in that they are considering the subset {$z_i$,...,$z_j$}. Isn't this case of comparison of $z_i$,$z_j$ getting too specific if we consider that specific subset only? I mean to say we are using randomized approach and the probability of comparison might be derived using a more broader look, such as a permutation of all possible cases or so.

That we are using a specific subset and that too sorted is not convincing as to how are we getting the correct probability for our algorithm...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

And the probability of $1/(j-i+1)$ -> total no. of elements in the subset is also fixed for specific $i$ and $j$

In considering the probability of comparison of $z_i$,$z_j$, the subset in which the two elements are there and which is to be partitioned can be anything(i.e composed of any possible element) and of any size (not just $j-i+1$)...

May be the randomization condition is actually taking everything in account but I am not getting it. Please can you explain me the logic they are using to find the said probability and also please convince me that we are correctly finding the probability of comparison.

For reference i am attaching the corresponding pages of INTRODUCTION TO ALGORITHMS 3RD ED-- CLRS

PAGE 182 PAGE 183 PAGE 184

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I feel like some context is missing. The first sentence I read is "Why are we considering the array as sorted?" and my reaction is: huh? What array? Who is considering it sorted? I'm not sure what that's referring to. You've included a long excerpt from a book but I'm not sure which part specifically you're referring to. Overall, I don't understand what you're asking, so I'm not sure how to answer... $\endgroup$ – D.W.♦ Apr 3 '20 at 20:33
  • $\begingroup$ I have edited my question @D.W. so please can you now say whether i am able to convey might doubt? $\endgroup$ – Abhishek Ghosh Apr 4 '20 at 6:07
  • $\begingroup$ The proof of Lemma 7.1 is only one paragraph long (it begins "By the discussion..." and ends "...line 4."), so I'm not sure what you mean by the 2nd paragraph of the proof of Lemma 7.1 $\endgroup$ – D.W.♦ Apr 4 '20 at 7:42
  • $\begingroup$ I don't see where the author is assuming the list is sorted. Exactly which sentence do you think is making this assumption? Can you quote it? $\endgroup$ – D.W.♦ Apr 4 '20 at 7:43
  • 1
    $\begingroup$ I recommend you don't use $...$ for emphasis or for text; instead, use *...*. $...$ is for mathematics. $lemma-7.1$ looks bad -- it gets the spacing wrong -- but lemma-7.1 looks OK. Just plain "Lemma 7.1" looks even better (to me) and matches the style used in the book. $\endgroup$ – D.W.♦ Apr 5 '20 at 18:17
2
$\begingroup$

A very simple proof: I claim that if there are d integers with values between x and y, and there are n ≥ 2 elements in the array, then the probability that x and y are compared is 2 / (d + 2), independent of n.

Proof by induction: If n = 2 then clearly d = 0, so the claim is that x and y are compared with probability 2 / (0 + 2) = 1. This is also clearly correct, since x and y must be compared.

Now let n ≥ 3. For the first partitioning, we choose a pivot at random. Every array element is compared against the pivot, and no other comparisons are made. So if by coincidence we choose x or y as the pivot, x and y will be compared. The probability for that is 2 / n. If by coincidence we choose one of the d elements with values between x and y, then the partitioning will move x to one partition and y to the other, so they are never compared. If we choose one of the other n - d - 2 elements, then x and y end up in the same partition, and by induction they will be compared with probability 2 / (d + 2).

So the probability that x and y are compared is 

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

That's of course the same result as Yuval's, since |j - i| = d + 1. The randomising makes the analysis quite easy - if we said for example "if n > 5 then we pick 5 elements at random and pick the median of those 5 as the pivot", the analysis would be much more complex.

PS. The proof in the paper is much easier: As you partition the array, $x_i$ and $x_j$ remain in the same sub-partition until a pivot with i <= pivot <= j is used. If that pivot is i or j then $x_i$ and $x_j$ are compared, otherwise they are not compared. So the chance is 2 / (abs (j-i) + 1).

Improve this answer
$\endgroup$
5
  • $\begingroup$ answer is quite elaborate which makes me to pin point at my doubt, u say- between $x$ and $y$ there are d elements; each such element $e$ has the property that $x$<$e$<$y$.(this is the assumption you do) Is it so that we can make that assumption strictly because of randomization( if so how? that is what I want to know)? Because original input array has all the elements as haphazard. I see that you write at end The randomizing makes the analysis quite easy I WANT TO KNOW THE CORRECTNESS OF CONSIDERATION OF PROBABIILITY USING THE RANDOMIZATION (IF ASSUMPTION IS BASED ON RANDOMIZATION). $\endgroup$ – Abhishek Ghosh Apr 6 '20 at 16:08
  • $\begingroup$ The problem which I had was as to how are we considering all the possible cases of comparison by simply assuming that the array is sorted?Now we take a certain instance of the array (sorted for simplicity).Then we choose a random variable $X_{ij}$ indicating $Z_i$ is compared with $Z_j$.Sum of all the $X_{ij}$ over all possible $i,j$ s shall give us the total number of comparisons i.e.running time of our algo for the instance we chose(sorted).Then we use Expectation to get the required number of comparison over all possible input arrays. Which the authors did quite implicitly. $\endgroup$ – Abhishek Ghosh Apr 24 '20 at 18:17
  • $\begingroup$ The rest is as gnasher729 and @Yuval said. $\endgroup$ – Abhishek Ghosh Apr 24 '20 at 18:23
  • 1
    $\begingroup$ after so many days I got the actual essence. Here authors are not considering a sorted instance of array, rather authors consider a subset of keys ; it is a set after all which is unordered. For a convenience we impose an ordering on the subset $Z_{ij}$. Note it isn't applicable to assume a sorted sub-array in this situation, however the concept of using a random general instance of a problem, then analyzing it; then using expectation to possibly include all other cases can be incorporated in some other situation.I don't delete previous comment as it shall remind me where I went wrong. $\endgroup$ – Abhishek Ghosh Jul 17 '20 at 6:50
  • 1
    $\begingroup$ Again thanks gnasher729 and @YuvalFilmus , for inculcating the correct thought process in me. $\endgroup$ – Abhishek Ghosh Jul 17 '20 at 6:51
2
$\begingroup$

The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is the $i$th smallest element in the array and that $y$ is the $j$th smallest element in the array, then the probability that $x,y$ are compared is $\frac{2}{|j-i|+1}$.

This is not a special case – every element $x$ in the array is the $i$th smallest element, for some value of $i$. This is just the pertinent information that allows us to calculate the probability that $x$ and $y$ are compared.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you please explain me as to how it turns out that we can compute the probabiiilty of comparison only given the order statistics of x,y, i.e., their relative order in the sorted array. How using our calculation on the relative ordering of the elements in the array is giving our required answer of probability of possible comparison between any $x$ and $y$ in the array. $\endgroup$ – Abhishek Ghosh Apr 4 '20 at 13:01
  • $\begingroup$ This is explained very well in the book. There is no need for me to repeat the explanation here. $\endgroup$ – Yuval Filmus Apr 4 '20 at 13:05
  • $\begingroup$ It is especially this part where I am having the problem. Please can you site the portion of the text from the book which specifically deals with it..What they just say is that for ease of analysis they rename the array elements as $z1$,$z2$,.. and they shall consider the set $Zij$. I also find an example about how choosing $z_i$ or $z_j$ in the set $Zij$ first as the pivot helps in their mutual comparison. Might be that it is there but I am unable to make it out. It shall be helpful if you please help. $\endgroup$ – Abhishek Ghosh Apr 4 '20 at 13:18
  • 1
    $\begingroup$ Consider the array $2,3,5,1,4$. Then $z_1 = 1$, $z_2 = 2$, $z_3 = 3$, $z_4 = 4$, $z_5 = 5$, and so we can write the array as $z_2,z_3,z_5,z_1,z_4$. The probability that $2 = z_2$ and $4 = z_4$ are compared is $1/|2-4|+1 = 1/3$. $\endgroup$ – Yuval Filmus Apr 4 '20 at 14:44
  • 1
    $\begingroup$ As another example, consider the array $20,30,50,10,40$. The probability that $20 = z_2$ and $40 = z_4$ are compared is still $1/3$. $\endgroup$ – Yuval Filmus Apr 4 '20 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.