Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The input is an array to be sorted, and we denote $z_i$ to be the $i$-th smallest element in the array. When deriving the probability that $z_i$ and $z_j$ are compared for $j > i$, we ignore elements outside of $$z_i, z_{i+1}, \ldots, z_{i+(j-i)}$$ How can we justify reducing the sample space? I understand that we simply do not care about those elements outside of $z_i, z_{i+1}, \ldots, z_{i+(j-i)}$ because they have no influence on the question of whether we get a compare between $z_i$ and $z_j$, but there is this sticking point that bothers me from a mathematical point of view. Is there a more rigorous argument for why we can ignore a whole subset of sample points?

For example, consider the following which illustrates the same concept that is at the heart of my question: Toss a 6-sided die. If 1 comes up, we win, if 2 comes up, we lose, and otherwise repeat. Clearly the probability we win is 1/2, but what exactly is going on when we ignore the faces 3 through 6? Is there a conditional probability argument working in the background?

share|cite|improve this question
Do you mean we ignore the existence of the other elements, or their values? The latter would be easier to explain than the former. It would help if you could link to the analysis you're talking about. – joriki Feb 17 '13 at 8:20
Please tell where this comes from, the standard analysis doesn't deal in probabilities (other than a bit of "as all cases are equally likely..."). – vonbrand Feb 17 '13 at 16:24
In the QuickSort algo, the probability that $z_i$ and $z_j$ is compared for $j>i$ is $2/(j-i+1)$. The reason is because if we pick an element between $z_i$ and $z_j$ to act as a pivot before we pick either $z_i$ or $z_j$, then $z_i$ and $z_j$ are fed into different recursive calls and never compared. I don't understand why we ignore $z_1$ up to $z_{i-1}$ and $z_{j+1}$ up to $z_{n}$ in the analysis, where $n$ is size of array. – Peter Feb 17 '13 at 20:31
Because the elements from $z_1$ to $z_{i-1}$ are smaller than both $z_i$ and $z_j$, so they never end up in different recursive calls. Same reasoning for the upper part. – Raskolnikov May 13 '13 at 4:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.