0
$\begingroup$

I would just like to discuss with you first part of the proof for quick sort please unless you need more details.

Probabilistic fact: For a quick sort please, given that the expected number of coin tosses in order to get $k$ heads is $2k$.

Definition:A good call to quick sort should give partitions each of size at most $\frac{3s}{4}$ where $s$ is the size of the sequence we want to sort. Bad call is at least $\frac{3s}{4}$.

Assumption: For a node of depth $i$, we have $i/2$ ancestors are good calls. Based on that, the size will be $(3/4)^{i/2}\times n$, where $n$ is the size of input sequence.

If a node $v$ of the quick-sort tree $T$ is associated with a “good” recursive call, then the input sizes of the children of $v$ are each at most $3s(v)/4$ (which is the same as $s(v)/(4/3))$, where $s(v)$ is the number of elements. Applying the probabilistic fact reviewed above, the expected number of invocations we must make until this occurs is $2 \log_{4/3}n$ (if a path terminates before this level, that is all the better).

Problems:

  1. Why is the expected number of invocations we must make until this occurs is $2 \log_{4/3}n$ ?
  2. What does it mean by "(if a path terminates before this level, that is all the better)"?
  3. Why it was expected that only $i/2$ ancestors of $i$ are good calls, and others are bad calls?
$\endgroup$
3
  • 1
    $\begingroup$ This analysis is very sloppy, and I suggest ignoring it. $\endgroup$ Oct 17, 2021 at 5:57
  • $\begingroup$ @YuvalFilmus. Thank you. Should I only have one question next time please because the question is voted against to be closed? $\endgroup$
    – Avv
    Oct 17, 2021 at 15:35
  • 1
    $\begingroup$ It depends on how related the questions are. $\endgroup$ Oct 17, 2021 at 15:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.