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.
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
$...$
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