Question

1. A. If we measure an instance size of computing the greatest common divisor of m and n by the size of the second number n, by how much can the size decrease after one iteration of Euclid’s algorithm? b. Prove that an instance size will always decrease at least by a factor of two after two successive iterations of Euclid’s algorithm

Answer 1

1. a. If we measure an instance size of computing the greatest common divisor of m and n by the size of the second number n, by how much can the size decrease after one iteration of Euclid’s algorithm? b. Prove that an instance size will always decrease at least by a factor of two after two successive iterations of Euclid’s algorithm. 2.Apply quick select to find the median of the list of numbers 9, 12, 5, 17, 20, 30, 8.

Step-by-step explanation: