How to understand the analysis of expected running time of randomized quick-sort in this paper? - Computer Science Stack Exchange

i'm learning book named data structures & algorithms in python.

on page 557-558, there proof of expected running time of randomized qucick-sort. have problems confusing me days. note them in bold form.

here's orginal text:

proposition 12.3: the expected running time of randomized quick-sort on sequence $s$ of size $n$ $o(n \log n)$.

justification: assume 2 elements of $s$ can compared in $o(1)$ time. consider single recursive call of randomized quick-sort, , let $n$ denote size of input call. call “good” if pivot chosen such subsequences $l$ , $g$ have size @ least $\frac{n}{4}$ , @ $\frac{3n}{4}$ each; otherwise, call “bad.”

now, consider implications of our choosing pivot uniformly @ random. note there $\frac{n}{2}$ possible choices pivot given call of size n of randomized quick-sort algorithm. thus, probability call $\frac{1}{2}$. note further call @ least partition list of size $n$ 2 lists of size $\frac{3n}{4}$ , $\frac{n}{4}$, , bad call bad producing single call of size $n−1$.

now consider recursion trace randomized quick-sort. trace defines binary tree, $t$, such each node in $t$ corresponds different recursive call on subproblem of sorting portion of original list.

say node $v$ in $t$ in size group $i$ if size of $v$’s subproblem greater $\left(\frac{3}{4}\right)^{i+1}n$ , @ $\left(\frac{3}{4}\right)^in$ let analyze expected time spent working on subproblems nodes in size group $i$. linearity of expectation (proposition a.19), expected time working on these subproblems sum of expected times each one. of these nodes correspond calls , correspond bad calls. note that, since call occurs probability $\frac{1}{2}$, expected number of consecutive calls have make before getting call $2$.

---

⓵ moreover, notice have call node in size group $i$, children in size groups higher $i$.

⓶ thus, element $x$ input list, expected number of nodes in size group $i$ containing $x$ in subproblems $2$. in other words, expected total size of subproblems in size group $i$ $2n$.

---

since nonrecursive work perform subproblem proportional size, implies total expected time spent processing subproblems nodes in size group $i$ $o(n)$.

the number of size groups $\log_{\frac{4}{3}}n$, since repeatedly multiplying $\frac{3}{4}$ same repeatedly dividing $\frac{4}{3}$. is, number of size groups $o(\log n)$. therefore, total expected running time of randomized quick-sort $o(n\log n)$. (see figure 11.13.)

here problems:

1. according sentence:

   ⓵ moreover, notice have call node in size group $i$, children in size groups higher $i$.

which size group node $s(a)$ belong to? , why?

2. ⓶ thus, element $x$ input list, expected number of nodes in size group $i$ containing $x$ in subproblems $2$. in other words, expected total size of subproblems in size group $i$ $2n$.

i can't understand meaning of sentence.

the root node corresponds subproblem of size $n$. larger $(3/4)^1 n$ , @ $(3/4)^0 n$, root node lies in group $0$.

given element $x$ , integer $i$, expected number of subproblems of group $i$ containing $x$ @ $2$. because if $p$ subproblem of group $i$ containing $x$ , $q$ child subproblem containing $x$, $q$ of group $i+1$ probability @ least $1/2$. (some calculation needed here.)

linearity of expectation shows expected total size of subproblems of group $i$ @ $2n$ — summing expected number of subproblems of group $i$ containing $x$ on possible elements. (you can understand if know linearity of expectation is.)