Here are two implementations of the classic Euclidean algorithm for computing the greatest common divisor: One which uses the mod operator, and one which does not: * GCD of m and n, where m > n *) fun gcd1 (m:int,n:int):int GCD of m and n ) fun gcd2(m:int,n:int) :int if n 0 then if n>m then gcd2 (n-m,m) else else if m>n gcd1 (n,m mod n) gcd2 (m-n,n) else Assume that (i) both algorithms terminate and are correct) a integer operations are constant time (independent of the sizes of the integers); and a integers are represented in binary (a) Let m and n, be the values of m and n respectively in the ith recursive call to gcd1. Prove that, if i+2 or more calls are made to gcd1, then n ni/2