Problem # In this problem you will establish the complexity of the Euclidean Algorithm. For your convenience, here is the procedure from class today: Basic_Euclid (m, n) a:= m; b := n; while b 0 do (a, b) := (b, a MOD b); end while; return a (a) Suppose a b. Explain why b+ a MOD b 2b . (a Dry b). (b) Show that part (a) implies that b+ a MOD b . (a + b). (c) Consider an input (m, n) to the algorithm, where m n. If Basic Euclid terminates after literations of the while loop, show that (m+n) > () (d) Deduce that Basic_Euclid terminates after O(log2(m+n)) iterations of the while loop. Problem # In this problem you will establish the complexity of the Euclidean Algorithm. For your convenience, here is the procedure from class today: Basic_Euclid (m, n) a:= m; b := n; while b 0 do (a, b) := (b, a MOD b); end while; return a (a) Suppose a b. Explain why b+ a MOD b 2b . (a Dry b). (b) Show that part (a) implies that b+ a MOD b . (a + b). (c) Consider an input (m, n) to the algorithm, where m n. If Basic Euclid terminates after literations of the while loop, show that (m+n) > () (d) Deduce that Basic_Euclid terminates after O(log2(m+n)) iterations of the while loop