0
$\begingroup$

After reading Why is the probability of two elements $y_i$, $y_j$ being compared equal to $2/(j - i + 1)$ in random quicksort?

I am confused as to what $j-i+1$ means in the denominator.

Is it the same as saying $$\frac{2}{\text{the total number of elements}}?$$ Isn't that a more simple notation as well?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It's all explained in the question. We have an unsorted list $[x_1, x_2, ..., x_n]$ and then sort it to obtain $[y_1, y_2, ..., y_n]$. For two elements $y_i$ and $y_j$ of this sorted list with $i < j$, the probability that $y_i$ and $y_j$ are compared to each other at some point is $2/(j - i + 1)$. This obviously depends on which two elements are chosen, since $i$ and $j$ will be different for each one.

$\endgroup$
2
  • $\begingroup$ so j-i+1 is the total number of elements in the range of $y_i$ and $y_j$? $\endgroup$
    โ€“ mathguy
    Commented Apr 25, 2020 at 0:03
  • $\begingroup$ @mathguy Yes, that's right $\endgroup$
    โ€“ SCappella
    Commented Apr 25, 2020 at 3:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .