Confusion about the definition of the average-case running time of algorithms

Question

In this lecture note,

The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$: $$T_{\text{average-case}}(n) = E_{|X| = n}[T(X)] = \sum_{|X| = n} T(X) \cdot Pr[X].$$

This wiki article (Quicksort) gives an average-case time complexity analysis for Quicksort:

When the input is a random permutation, the rank of the pivot is uniform random from $0$ to $n − 1$. Then the resulting parts of the partition have sizes $i$ and $n − i − 1$, and $i$ is uniform random from $0$ to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation: $$C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)).$$

My confusion is how does the average-case analysis for Quicksort fit the definition above? First, I would expect a term $\frac{1}{n!}$ (which is $Pr[X]$) in the recurrence. But, it is not the case. Second, the analysis above is on a random permutation and the averaging is done over all possible splits. How is this related to averaging over all possible inputs? Do I need another definition for average-case running time?

Answer 1

The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as $$ \newcommand{\Tavg}{T_{\mathit{avg}}} \newcommand{\EE}{\mathbb{E}} \Tavg(n) = \sideset{\EE}{}{}_{X \sim \mu_n} [T(X)]. $$ Usually $\mu_n$ is supported on inputs of "length" $n$, though length is not necessarily measured in bits or in machine words.

When analyzing comparison-based sorting algorithms, usually $\mu_n$ is chosen as the uniform distribution over all permutations of the array $1,2,\ldots,n$ (or any other array consisting of $n$ distinct comparable elements). The analysis of quicksort uses these distributions.

Now regarding the recursive formula you mention. Given an input array $X$, let $I$ be the rank of the pivot; if $X$ is a random variable, then so is $I$. The formula in Wikipedia is $$ \Tavg(n) = \sum_{i=0}^{n-1} \Pr[I=i] \EE[T(X)|I=i] = \sum_{i=0}^{n-1} \frac{1}{n} \left[n-1 + \Tavg(i) + \Tavg(n-1-i)\right]. $$ Rearranging gives you the quoted formula.

Answer 2

Let $U_n$ be the set of all inputs of size $n$. Suppose $S_n^i$ are some partition of $U_n$ (indexed by $i$), such that each member of $S_n^i$ takes time $T(n, i)$. We can write the expected time formula like $$T_{average\text{-}case}(n) = \sum_{X \in U_n}{T(X) Pr(X)} = \sum_{S_n^i} \sum_{X \in S_n^i} T(n, i) Pr(X) = \sum_{S_n^i} T(n, i) Pr(S_n^i) $$

In your case, $S_n^i$ is the set of inputs of length $n$ with the chosen pivot being the $i$th (0-based) largest element, $Pr(S_n^i) = 1/n$, and $T(n, i) = C(i) + C(n - i - 1)$.

Answer 3

Shorn of all formulae, the difference is this:

The general definition of average running time for an algorithm on inputs of size N is direct: It is the sum of the running times of each specific input of size N, weighted by that input's probability. Note that this definition makes no reference whatsoever to what the algorithm actually does with each specific input, nor does it propose any relationships between average running times for different input sizes.

The recurrence relation of average running time for Quicksort on inputs of size N is INdirect: It computes the average running time for size N as a function of the average running times for sizes smaller than N. In effect, the running times of specific inputs of size N are calculated from the running times of sections of those inputs of smaller size, base on the partition; then all of those section times are re-grouped by size and weighted sums taken for each grouping. All references to the probabilities of specific inputs are buried behind the averages.