Exact definition of average time complexity?

Question

Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least.

Here is a definition that I feel comfortable with:

Consider a set $A$ of finite elements, with each $a\in A$ indicating individual input cases. There exists a function $T(a)\mapsto t\in\mathbb{N}$, i.e., running time for individual cases. Now we can define the average running time of input set to be simply $$\overline{T}(A)=\frac{\sum\limits_{a\in A}T(a)}{\#A},$$ where $\#A$ denotes number of elements in $A$. For example, in QuickSort, we let $A_n=\{\text{array of $n$ unsorted integers}\}=\mathbb{Z}^n$.

But now we have to do an additional step. An integer can take on an infinite set of values, so we naturally consider the memory constraint and instead confine each integer $i$ to be $L\le i\le U$. Now $\#(A_n)=(U-L+1)^n$, and we have a clearly defined $T(\cdot)$, and we can try to figure out $\overline{T}(A_n)$, although this is a very tough combinatorics problem.

We can also consider $i$ to be a bounded real number, with the modification $\#(A_n)=\mu_{\text{Le}}(A_n)=(U-L)^n$, and $$ \overline{T}(A_n)=\frac{1}{(U-L)^n}\int\limits_{a\in A_n}T(a)\,\mathrm{d}\mu_{\text{Le}}. $$

What CS people did instead, is stating $T(a) \le T(\text{head})+T(\text{tail})+cn$ for some $c$, then simply averaging $T(\text{head})$ and $T(\text{tail})$ for varying head or tail lengths. This is stating implicitly somehow varying head (or tail) lengths are "equally likely", with out even considering the constraint that makes $A_n$ finite. This is like saying you can pick an odd number from the set of all integers at "$50\%$ probability" without even bothering to define what this "probability" means!

So how is this average time complexity rigorously defined over an infinite, countable number of cases?

If average time complexity is dependent on a set of rules of translating clearly defined recursion to what is essentially an intuitive ad-hoc definition each time, how can we define average time complexity for arbitrary code?

Answer 1

Here is the definition of average-case time complexity of an algorithm:

Let $T(x)$ be the running time of some algorithm $A$ on input $x$. For every $n$, let $\mu_n$ be a distribution on inputs of length $n$. The average-case or expected time complexity of $A$ on inputs of length $n$ is $$T_{\mathit{avg}}(n) := \mathbb{E}_{x \sim \mu_n} T(x). $$

As you can see, in order to talk about average-case complexity, you have to specify a distribution. In the definition above I have alluded to the common case in which the complexity is parameterized by input length, but we could also have more parameters, or no parameters at all.

For comparison-based sorting algorithms, we usually consider the following distribution $\mu_n$: the uniform distribution on all $n!$ permutations of $1,\ldots,n$. However, we would obtain exactly the same notion of average-case complexity (for comparison-based algorithms) if instead we pick any atom-less distribution $\mu$, and define $\mu_n$ to consist of $n$ iid copies of $\mu$.

Unfortunately, no distribution on the integers is atom-less. This creates a problem, since if we generate $n$ iid copies of a distribution $\mu$ with atoms, then there is positive probability that the generated elements are not distinct. While comparison-based sorting algorithms can certainly handle this case, the situation becomes much less clean since the average-case time complexity now depends on $\mu$.

Finally, you seem to be quoting a quite informal average-case complexity analysis of quicksort. You can find rigorous analysis of the average-case complexity of quicksort (in fact, two different ones) in lecture notes of Avrim Blum.

Answer 2

As expected value of random variable.

1. Donald E.Knuth The Art of Computer Programming, volume 1, 1997, page 98, Chapter 1, section 1.2.10.
2. Tim Roughgarden — Algorithms Illuminated, Part 1, page 190.