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

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?

• The usual rule is one question per post. I only answered your last question, regarding the definition of average-case running time. Mar 28, 2017 at 10:19
• @YuvalFilmus Thanks. However, I think these questions are closely related, being specific confusions about the definitions of average-case running time. Mar 28, 2017 at 11:43

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.

• Thanks. However, I am still confused about the definitions. According to $T_{avg}(n) = E_{X \sim \mu_{n}} [T(X)]$, I would expect $T_{avg}(n) = \frac{1}{n!} \sum_{X \in U_n}T(X)$ given that $\mu_{n}$ is chosen as the uniform distribution over $U_{n}$, the set of all possible permutations. What is wrong here? Mar 28, 2017 at 11:40
• I think the equality $$\newcommand{\Tavg}{T_{\mathit{avg}}} \newcommand{\EE}{\mathbb{E}} \Tavg(n) = \sideset{\EE}{}{}_{X \sim \mu_n} [T(X)] = \sum_{i=0}^{n-1} \Pr[I=i] \EE[T(X)|I=i]$$ solves my confusion. It is "computing expectation by conditioning". Isn't it? Thanks. Mar 28, 2017 at 12:16
• Right, that's exactly what is happening there. Mar 28, 2017 at 12:17
• @YuvalFilmus Can you please explain in the definition of average-case time complexity what the expression on the right means? I know it's the mathematical expectation of some random variable but what is that variable? what does $T(X)$ mean?
Jul 24, 2021 at 17:14

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)$.

• $U_{n}$ is the set of all inputs of size $n$. $S_n^{i}$ are some partition of $U_n$. I don't understand what $S_n^{i}$ are/is? In the formula, you write $X \in S_n^{i}$. It seems that $S_{n}^{i}$ is a set. But, a set of what? Mar 28, 2017 at 11:30
• Mar 29, 2017 at 2:49

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.