Chapter 8.4

|    |   A |   |   | B         |
|----+-----+---+---+-----------|
|  1 | .79 |   | 0 |           |
|  2 | .13 |   | 1 | (.13 .16) |
|  3 | .16 |   | 2 | (.20)     |
|  4 | .64 |   | 3 | (.39)     |
|  5 | .39 |   | 4 | (.4)      |
|  6 | .20 |   | 5 | (.53)     |
|  7 | .89 |   | 6 | (.64)     |
|  8 | .53 |   | 7 | (.79 .71) |
|  9 | .71 |   | 8 | (.89)     |
| 10 |  .4 |   | 9 |           |
|----+-----+---+---+-----------|

The worst case appears when all elements fall in one bucket, the worst-case running time is \(\Theta(n^2)\).

We could use \(O(n\lg n)\) sorting algorithm like heapsort or merge sort instead of insertion sort as the intermediate sorting algorithm, then we preserve the linear average-case running time and make the worst-case running time \(O(n\lg n)\).

We define indicator random variable

\begin{align*} X_i &= I\{\text{got head in the ith flip of coin}\} \end{align*}

The indicator random variable \(X_i\) is \(1\) with probability \(1/2\) and \(0\) with probability \(1/2\). We have

\begin{align*} E[X^2] &=E\Bigg[\bigg(\sum_{i=1}^{2}X_i\bigg)^2\Bigg]\\ &=E\bigg[\sum_{i=1}^{2}X_i^2 +\sum_{1\leq i\leq 2}\sum_{1\leq j\leq 2,\ j\neq i}X_i X_j\bigg]\\ &=\sum_{i=1}^{2}E[X_i^2] +\sum_{1\leq i\leq 2}\sum_{1\leq j\leq 2,\ j\neq i}E[X_i X_j]\\ &=2\times(1)^2\times(1/2)+2\times(2-1)\times(1/2)^2\\ &=3/2 \end{align*}

and

\begin{align*} E^2[X] &=(E[X])^2\\ &=\Bigg(E\bigg[\sum_{i=1}^{2} X_i\bigg]\Bigg)^2\\ &=\bigg(\sum_{i=1}^{2} E[X_i]\bigg)^2\\ &=(2\times (1/2))^2\\ &=1 \end{align*}

Sort the \(n\) points by their distances \(d_i = \sqrt{x_i^2 + y_i^2}\), we define the \(n\) buckets, which for \(k = 1..n\), the \(k\)th bucket is

\begin{align*} B_k &= \Bigg\{(x_i,y_i) \bigg|\sqrt{\frac{k-1}{n}}\leq d_i\leq\sqrt{\frac{k}{n}}\Bigg\} \end{align*}

The \(n\) buckets divide the circle region into \(n\) regions which have the same areas, thus a point has equal probability to fall into any bucket, the average-case running time of the bucket sort algorithm is \(\Theta(n)\).

We sort the \(n\) random variables with bucket sort by \(P(x)\), such we know that a variable has the same probability to fall into each bucket, thus the average-case running time is linear.