# Question

Insertion sort can be expressed as a recursive procedure as follows. In order to sort A [1 ¬ n], we recursively sort A [1 ¬n -1] and then insert A[n] into the sorted array A [1 ¬ ¬n – 1]. Write a recurrence for the running time of this recursive version of insertion sort.

## Answer to relevant Questions

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. ...Show that for any real constants a and b, where b > 0, (3.2) (n + a)b = Θ (nb).Suppose that you want to output 0 with probability 1/2 and 1 with probability 1/2. At your disposal is a procedure BIASED-RANDOM, that outputs either 0 or 1. It outputs 1 with some probability p and 0 with probability 1 - p, ...Professor Armstrong suggests the following procedure for generating a uniform random permutation: PERMUTE-BY-CYCLIC (A) 1 n ← length [A] 2 offset ← RANDOM (1, n) 3 for i ← 1 to n 4 do dest ← i + ...Suppose that the splits at every level of quick sort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg ...Post your question

0