Problems
5-1
a
Let's define the indicator random variable $X_i$, for $1 \leq i \leq n$, by:
$$ \begin{eqnarray} X_i &=& I\lbrace\text{the INCREMENT operation increases the counter}\rbrace \\ &=& \begin{cases} n_{i + 1} - n_i, & \text{the INCREMENT operation increases the counter} \\ 0, & \text{otherwise} \end{cases} \end{eqnarray} $$
We have:
$$ \begin{eqnarray} E[X_i] &=& 0 * Pr\lbrace \text{the INCREMENT operation doesn't increase the counter} \rbrace + \\ && (n_{i + 1} - n_i) * Pr\lbrace \text{the INCREMENT operation increases the counter} \rbrace \\ &=& 0 * (1 - \frac{1}{n_{i + 1} - n_i}) + (n_{i + 1} - n_i) * \frac{1}{n_{i + 1} - n_i} \\ &=& 1 \end{eqnarray} $$
Let X be the random variable as the expected value represented by the counter, we have $X = \sum_{i = 1}^{n}X_i$. So:
$$ \begin{eqnarray} E[X] &=& E[\sum_{i = 1}^{n}X_i] \\ &=& \sum_{i = 1}^{n}E[X_i] \\ &=& \sum_{i = 1}^{n}1 \\ &=& n \end{eqnarray} $$
b
$$ \begin{eqnarray} Var(X_i) &=& E[X_i^2] - (E[X_i])^2 \\ &=& 0^2 * (1 - \frac{1}{n_{i + 1} - n_i}) + (n_{i + 1} - n_i)^2 * \frac{1}{n_{i + 1} - n_i} - 1^2 \\ &=& 100^2 * \frac{1}{100} - 1^2 \\ &=& 99 \end{eqnarray} $$
Because the random variables $X_i$ are uncorrelated, so $Var(X) = Var(\sum_{i = 1}^{n}X_i) = \sum_{i = 1}^{n}Var(X_i) = \sum_{i = 1}^{n}99 = 99n$.
5-2
a
RANDOM-SEARCH(A, x)
n = A.length
let B[1..n] be new array
while B is not full
i = RANDOM(1, n)
B[i] = i
if A[i] = x
return i
return -1
b
This is similar like the question "How many balls must we toss, an the average, until a given bin contains a ball?", the answer is n.
c
Each time when we pick an index, we have the probability $\frac{k}{n}$ such that we find x in A. So according to C.32, it takes $\frac{1}{\frac{k}{n}} = \frac{n}{k}$ trials before we find x.
d
This is similar like the question "How many balls must we toss until every bin contains at least one ball?", the answer is $n(\ln{n} + O(1))$.
e
The best-case running time is 1, and the worst-case running time is n, thus the average-case running time is $\frac{n + 1}{2}$.
f
The best-case running time is 1, and the worst-case running time is n - k + 1. The average-case running time is $\frac{n + 1}{k + 1}$, here is the discussion.
g
If there are no indices i such that A[i] = x, then it always scans all elements in A, thus the average-case and worst-case running time are both n.
h
The worst-case running time is the same as DETERMINISTIC-SEARCH, the expected-case running time is the average-case running time in DETERMINISTIC-SEARCH.
i
The DETERMINISTIC-SEARCH. It has better average-case running time, and the SCRAMBLE-SEARCH takes additional time to permute the array.