Review:

Average-case Running Time

1. Define sample space $S_n$: All inputs of size $n$ Each input $x\in S_n$, $t(x)$ is a random variable
   • Simplification: Define one input for each possible behavior (e.g. search([1, 2, 3], 1) and search([10, 20, 30], 10) have the same behavior)
2. Given a probability distribution over $S_n$, $t_n=E[t(x)]=\sum_{x\in S_n} t(x)\cdot P(x)$ is the average-case runtime for size $n$ ”Let n be arbitary”
   • If not given, use a uniform distribution.
3. $t(x)$ need to be exact (without constant factors)
   • Pick “representative operations” so that the total running time is within a constant factor

Examples

QuickSort:

• Sample Space Sn = {all permutations of [1,2,…,n]}
• Uniform probability distribution
• T(A) = Total number of comparisons between elements
• Indicator Random Variable: $X_{i,j}=$ 1 if i is compared to j, 0 otherwise
• $T(A)=\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}X_{i,j}$
• $E[T(A)]=\sum_{i=1}^{n-1} \sum_{j=i+1}^{n}(E[X_{i,j}] =P[X_{i,j}=1])$
• $P[X_{i,j}=1]= \frac{2}{j-i+1}$ (i, j belonging to the same sublist and one is selected before any others in between)

Randomized QuickSort: Since we don’t know the samples’ distribution, choose pivots at random to ensure the O(n log n) time

Amortized Analysis

Worst-case Sequence Complexity: Max total runtime to perform m operations from fixed starting point (typically start empty).

• WCSC ≤ m * worst-case of a single operation

Amortized Analysis: Total sequence complexity when the worst time of individual elements are far larger than the average