2
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – hengxin Mar 28 '17 at 11:40
  • $\begingroup$ This formula is true but unhelpful. I'll update my answer with some more information. $\endgroup$ – Yuval Filmus Mar 28 '17 at 11:45
  • 1
    $\begingroup$ 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. $\endgroup$ – hengxin Mar 28 '17 at 12:16
  • $\begingroup$ Right, that's exactly what is happening there. $\endgroup$ – Yuval Filmus Mar 28 '17 at 12:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ $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? $\endgroup$ – hengxin Mar 28 '17 at 11:30
  • $\begingroup$ @hengxin en.wikipedia.org/wiki/Partition_of_a_set $\endgroup$ – feersum Mar 29 '17 at 2:49
0
$\begingroup$

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.

$\endgroup$

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.