随机算法 (Fall 2011)/Randomized Quicksort

From EtoneWiki
Revision as of 06:03, 27 August 2011 by WikiSysop (talk)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Given as input a set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} numbers, we want to sort the numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} in increasing order. One of the most famous algorithm for this problem is the Quicksort algorithm.

  • if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|>1} do:
    • pick an Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x\in S} as the pivot;
    • partition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{x\}} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} , where all numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} are smaller than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and all numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} are larger than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} ;
    • recursively sort Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} ;

The time complexity of this sorting algorithm is measured by the number of comparisons.

For the deterministic quicksort algorithm, the pivot is picked from a fixed position (e.g. the first number in the array). The worst-case time complexity in terms of number of comparisons is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Theta(n^2)} .

Algorithm: RandQSort

We consider the following randomized version of the quicksort.

  • if Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle |S|>1} do:
    • uniformly pick a random Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x\in S} as the pivot;
    • partition Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{x\}} , and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} , where all numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} are smaller than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} and all numbers in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} are larger than Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle x} ;
    • recursively sort Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} ;

Analysis

Our goal is to analyze the expected number of comparisons during an execution of RandQSort with an arbitrary input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . We achieve this by measuring the chance that each pair of elements are compared, and summing all of them up due to Linearity of Expectation.

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} denote the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle i} th smallest element in Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} . Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{ij}\in\{0,1\}} be the random variable which indicates whether Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are compared during the execution of RandQSort. That is:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} X_{ij} &= \begin{cases} 1 & a_i\mbox{ and }a_j\mbox{ are compared}\\ 0 & \mbox{otherwise} \end{cases}. \end{align} }

Elements Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are compared only if one of them is chosen as pivot. After comparison they are separated (thus are never compared again). So we have the following observation:

Claim 1: Every pair of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are compared at most once.

Therefore the sum of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{ij}} for all pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{i, j\}} gives the total number of comparisons. The expected number of comparisons is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right]} . Due to Linearity of Expectation, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right] = \sum_{i=1}^n\sum_{j>i}\mathbf{E}\left[X_{ij}\right]} . Our next step is to analyze Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathbf{E}\left[X_{ij}\right]} for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{i, j\}} .

By the definition of expectation and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle X_{ij}} ,

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \mathbf{E}\left[X_{ij}\right] &= 1\cdot \Pr[a_i\mbox{ and }a_j\mbox{ are compared}] + 0\cdot \Pr[a_i\mbox{ and }a_j\mbox{ are not compared}]\\ &= \Pr[a_i\mbox{ and }a_j\mbox{ are compared}]. \end{align}}

We are going to bound this probability.

Claim 2: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are compared if and only if one of them is chosen as pivot when they are still in the same subset.

This is easy to verify: just check the algorithm. The next one is a bit complicated.

Claim 3: If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are still in the same subset then all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} are in the same subset.

We can verify this by induction. Initially, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} itself has the property described above; and partitioning any Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} with the property into Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} will preserve the property for both Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_1} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S_2} . Therefore Claim 3 holds.

Combining Claim 2 and 3, we have:

Claim 4: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} are compared only if one of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_j\}} is chosen from Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} .

And apparently,

Claim 5: Every one of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} is chosen equal-probably.

This is because our RandQSort chooses the pivot uniformly at random.

Claim 4 and Claim 5 together imply:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \Pr[a_i\mbox{ and }a_j\mbox{ are compared}] &\le \frac{2}{j-i+1}. \end{align}}
Remark: Perhaps you feel confused about the above argument. You may ask: "The algorithm chooses pivots for many times during the execution. Why in the above argument, it looks like the pivot is chosen only once?" Good question! Let's see what really happens by looking closely.

For any pair Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_i} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_j} , initially Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} are all in the same set Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} (obviously!). During the execution of the algorithm, the set which containing Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} are shrinking (due to the pivoting), until one of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} is chosen, and the set is partitioned into different subsets. We ask for the probability that the chosen one is among Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_j\}} . So we really care about "the last" pivoting before Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} is split.

Formally, let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} be the random variable denoting the pivot element. We know that for each Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle a_k\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y=a_k} with the same probability, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y\not\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} with an unknown probability (remember that there might be other elements in the same subset with Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} ). The probability we are looking for is actually Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \Pr[Y\in \{a_i, a_j\}\mid Y\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}]} , which is always Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \frac{2}{j-i+1}} , provided that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle Y} is uniform over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}} .

The conditional probability rules out the irrelevant events in a probabilistic argument.

Summing all up:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align} \mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right] &= \sum_{i=1}^n\sum_{j>i}\mathbf{E}\left[X_{ij}\right]\\ &\le \sum_{i=1}^n\sum_{j>i}\frac{2}{j-i+1}\\ &= \sum_{i=1}^n\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\mbox{Let }k=j-i+1)\\ &\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\ &= 2n\sum_{k=1}^{n}\frac{1}{k}\\ &= 2n H(n). \end{align}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle H(n)} is the Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} th Harmonic number. It holds that

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \begin{align}H(n) = \ln n+O(1)\end{align}} .

Therefore, for an arbitrary input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle n} numbers, the expected number of comparisons taken by RandQSort to sort Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle S} is Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "http://tcs.nju.edu.cn:7231/localhost/v1/":): {\displaystyle \mathrm{O}(n\log n)} .