1. Correctness of given algorithm 2. Find the running time of the algorithm 3. Write a recursive version of the same algorithm.

(10 points) 4. The greatest common divisor (GCD) of two positive integers, if you remember your elementary arithmetic, is the largest positive integer that divides both the given numbers. An algorithm for computing GCD is given as follows: unsigned int gcd(unsigned int n, unsigned int m) if (n--0) return m; if (m = 0) return n; while (mn) if (n>m) n = n-m; else mm-n; return n; Argue about the correctness of the algorithm, either rigorously or through non-trivial examples. Obtain as tight an order as possible for the running time of the algorithm. Write a recursive version of the same algorithm