1
$\begingroup$

This is related to the discussion of average case of quick sort. Given that we have a sorted sub-array $Z_{ij} = i, i+1, \dots, j$ where $i < j$.

Claim: $i$ and $j$ are compared if and only if, among all elements in $Z_{ij}$, the first element to be picked as a pivot is either $i $ or $ j$.

Forward direction Proof: The “only if”: suppose the first one picked as pivot is some $k $ that is between $i$ and $j$, then $i $ and $ j$ will be separated into different partitions and will never meet each other.

Problem 1: For backward direction above, I understand that it should be that if the first element to be picked as a pivot is either $i $ or $ j$, then $i$ and $j$ are compared. So I am not sure why the "only if" part was stated as above please?

Backward direction Proof: The “if”: if $i$ is chosen as pivot (the first one among $Z_{ij}$), then $ j$ will be compared to pivot $i$ for sure, because nobody could have possibly separated them yet!

Then we can proceed and define $X$ to be the total number of comparisons and so on until we have $O(n\log{n})$ complexity, which is clear once the above claim is understood, which I have some issues with please.

If $i$ that is chosen as a pivot guarantees based on the proof that we will get $O(n\log n)$ complexity based on the condition that $i$ is the first element to be a pivot and $j$ to be after $i$, then we can see that $E[X_{ij}] = \Pr(i \text{ or } j)$, where $\Pr$ back means the probability that either $i$ or $j$ to be the first pivot and both at the beginning and at the end of the array.

$$E[X] = \Sigma_{i}\Sigma_{j=i+1}E[X_{ij}] = \frac{2}{j-1+1}$$

Claim 2: Now in the randomized case, we can assume a less clever assumption (which I don't understand) that: Given that $n$ is the number of elements to be sorted and $T(n)$ is expected time to sort $n$ elements. First pivot chooses $i$th smallest element, all equally likely. Then:

$$T(n) = (n-1) + \frac 1n \sum_{i=0}^{n-1}(T(i)+T(n-i-1))$$ $$= (n-1) + \frac 2n \sum_{i=1}^{n-1}(T(i))$$

Problem 2: how the previous claim is less clever than the first one please? And how $T(n)$ above is formulated?

Problem 3: how $T(n)$ becomes $T(n)= (n-1) + \frac 2n \sum_{i=1}^{n-1}(T(i))$

$\endgroup$
2
  • $\begingroup$ Problem 2 is unanswerable – which claim is more clever is completely subjective. $\endgroup$ Oct 2 at 10:57
  • 1
    $\begingroup$ Problem 3 you can solve on your own. Try harder. $\endgroup$ Oct 2 at 10:57
1
$\begingroup$

The claim is proved as follows (in reverse order):

  • If the first element among $Z_{ij}$ to be chosen as pivot is $i$ or $j$, then $i$ and $j$ are compared.
  • If the first element among $Z_{ij}$ to be chosen as pivot is not $i$ or $j$, then $i$ and $j$ are not compared.

The forward direction is the contrapositive of the "only if" implication.


Being clever or not is subjective rather than technical. I would just ignore this designation.


Perhaps unrolling the sums would help you prove the identity:

$$ T(0) + T(n-1) + T(1) + T(n-2) + \cdots + T(n-1) + T(0) = 2(T(0) + T(1) + \cdots + T(n-1)). $$

$\endgroup$
1
  • $\begingroup$ Thank you very much. I see that $T(0) + T(n-1), ...T(n-1)+T(0)$, so have 2 of each and thus we got 2 multiplied by sum please? If this is true, so this "less clever" approach is basically assumin pivot can be any element and thus $T(i) + T(n-i-1)$ please? $\endgroup$
    – Avra
    Oct 2 at 16:36

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.