# Question: Professor Marceau objects to the loop invariant used

Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray contains no 0-permutations. Therefore, the probability that an empty subarray contains a 0-permutation should be 0, thus invalidating the loop invariant prior to the first iteration. Rewrite the procedure RANDOMIZE-IN-PLACE so that it’s associated loop invariant applies to a nonempty subarray prior to the first iteration, and modify the proof of Lemma 5.5 for your procedure.

## Answer to relevant Questions

Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray ...Show that an n-element heap has height [lg n].Why do we analyze the average-case performance of a randomized algorithm and not its worst-case performance?What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time O(n lg n)?Suggest how storage for elements can be allocated and deal located within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two ...Post your question