2
$\begingroup$

I'm learning the book named Data Structures & Algorithms in Python.

On Page 557-558, there is a proof of the expected running time of randomized qucick-sort. I have some problems confusing me some days. I will note them in bold form.

Here's orginal text:

Proposition 12.3: The expected running time of randomized quick-sort on a sequence $S$ of size $n$ is $O(n \log n)$.

Justification: We assume two elements of $S$ can be compared in $O(1)$ time. Consider a single recursive call of randomized quick-sort, and let $n$ denote the size of the input for this call. Say that this call is “good” if the pivot chosen is such that subsequences $L$ and $G$ have size at least $\frac{n}{4}$ and at most $\frac{3n}{4}$ each; otherwise, a call is “bad.”

Now, consider the implications of our choosing a pivot uniformly at random. Note that there are $\frac{n}{2}$ possible good choices for the pivot for any given call of size n of the randomized quick-sort algorithm. Thus, the probability that any call is good is $\frac{1}{2}$. Note further that a good call will at least partition a list of size $n$ into two lists of size $\frac{3n}{4}$ and $\frac{n}{4}$, and a bad call could be as bad as producing a single call of size $n−1$.

Now consider a recursion trace for randomized quick-sort. This trace defines a binary tree, $T$, such that each node in $T$ corresponds to a different recursive call on a subproblem of sorting a portion of the original list.

Say that a node $v$ in $T$ is in size group $i$ if the size of $v$’s subproblem is greater than $\left(\frac{3}{4}\right)^{i+1}n$ and at most $\left(\frac{3}{4}\right)^in$ Let us analyze the expected time spent working on all the subproblems for nodes in size group $i$. By the linearity of expectation (Proposition A.19), the expected time for working on all these subproblems is the sum of the expected times for each one. Some of these nodes correspond to good calls and some correspond to bad calls. But note that, since a good call occurs with probability $\frac{1}{2}$, the expected number of consecutive calls we have to make before getting a good call is $2$.


⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.


Since the nonrecursive work we perform for any subproblem is proportional to its size, this implies that the total expected time spent processing subproblems for nodes in size group $i$ is $O(n)$.

The number of size groups is $\log_{\frac{4}{3}}n$, since repeatedly multiplying by $\frac{3}{4}$ is the same as repeatedly dividing by $\frac{4}{3}$. That is, the number of size groups is $O(\log n)$. Therefore, the total expected running time of randomized quick-sort is $O(n\log n)$. (See Figure 11.13.)

**Figure 12.13:** A visual time analysis of the quick-sort tree $T$. Each node is shown labeled with the size of its subproblem.

Here are my problems:

  1. According this sentence:

    ⓵ Moreover, notice that as soon as we have a good call for a node in size group $i$, its children will be in size groups higher than $i$.

Which size group does node $s(a)$ belong to? And why?

  1. ⓶ Thus, for any element $x$ from the input list, the expected number of nodes in size group $i$ containing $x$ in their subproblems is $2$. In other words, the expected total size of all the subproblems in size group $i$ is $2n$.

I can't really understand the meaning of this sentence.

$\endgroup$

migrated from stackoverflow.com Aug 21 '17 at 9:11

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ I recommend you pick up an algorithms textbook that focusses on analysis, e.g. Sedgewick's. $\endgroup$ – Raphael Aug 21 '17 at 11:55
  • $\begingroup$ s(a) belongs to group 0 as blue dashed line suggests. It must be a product of a “bad call” containing > 75 % of S (size of nodes are somewhat proportional to size of subproblems). Sedgewick takes different approach (p. 23) than Goodrich here. $\endgroup$ – Mr. Tao Aug 25 '17 at 15:07
1
$\begingroup$

The root node corresponds to a subproblem of size $n$. This is larger than $(3/4)^1 n$ and at most $(3/4)^0 n$, so the root node lies in group $0$.

Given any element $x$ and any integer $i$, the expected number of subproblems of group $i$ containing $x$ is at most $2$. This is because if $P$ is a subproblem of group $i$ containing $x$ and $Q$ is its child subproblem containing $x$, then $Q$ is of group $i+1$ with probability at least $1/2$. (Some calculation is needed here.)

Linearity of expectation shows that the expected total size of all subproblems of group $i$ is at most $2n$ — we get this by summing the expected number of subproblems of group $i$ containing $x$ over all possible elements. (You can only understand this if you know what linearity of expectation is.)

$\endgroup$
  • $\begingroup$ Which size group does node S(a) belong to ? And why? I can't figure out. $\endgroup$ – Jesse Aug 21 '17 at 15:43
  • $\begingroup$ It's impossible to tell in general, since it depends on how the root was split. In the figure, though, it is indicated that it belongs to group 0. $\endgroup$ – Yuval Filmus Aug 21 '17 at 16:13
  • $\begingroup$ Why does it belong to group 0? Accroding to author's words, if node S(r) have a good call, its children will be in size groups higher than i. Since S(a) is its child, it should be in group 1. $\endgroup$ – Jesse Aug 21 '17 at 18:21
  • $\begingroup$ It must have had a bad call, then. $\endgroup$ – Yuval Filmus Aug 21 '17 at 18:22
  • $\begingroup$ Then since all the nodes of third level are in size group higher than the parent nodes in the second level, so they should be the outcome of good call. If my thought is right, then the nodes of fourth level should be the outcome of bad call from the nodes of thrid level? If so, the laws is that good call and bad call happen in turn. Is it right? $\endgroup$ – Jesse Aug 21 '17 at 19:10

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.