# Randomized Quick Sort Discussion

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?
• This analysis is very sloppy, and I suggest ignoring it. Oct 17, 2021 at 5:57
• @YuvalFilmus. Thank you. Should I only have one question next time please because the question is voted against to be closed?
– Avv
Oct 17, 2021 at 15:35
• It depends on how related the questions are. Oct 17, 2021 at 15:36