Chapter 10, Problem 3P

(a)

Program Plan Intro

To argue that COMPACT-LIST-SEARCH ( L , n , k ) returns same answer for both for and while loops and total number of iterations is at least t

(b)

Program Plan Intro

To argue that expected running time of COMPACT-LIST-SEARCH’ ( L , n , k , t ) is $O(t+E\left[X_t\right])$ .

(c)

Program Plan Intro

To show that $E\left[X_t\right]\le {\displaystyle {\sum }_{r=1}^n{\left(1-r/n\right)}^t}$ .

(d)

Program Plan Intro

To show that ${\displaystyle {\sum }_{r=0}^{n-1}{r}^t}\le n^{t+1}/\left(t+1\right)$ .

(e)

Program Plan Intro

To prove that $E\left[X_t\right]\le n/\left(t+1\right)$ .

(f)

Program Plan Intro

To show that COMPACT-LIST-SEARCH’ ( L , n , k , t ) runs in $O\left(t+n/t\right)$ expected time.

(g)

Program Plan Intro

To conclude that COMPACT-LIST-SEARCH runs in $O\left(\sqrt{n}\right)$ expected time.

(h)

Program Plan Intro

To argue that random skips do not necessarily help asymptotically when list contains repeated key values.