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 '21 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 '21 at 15:35
  • 1
    $\begingroup$ It depends on how related the questions are. $\endgroup$ Oct 17 '21 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.