ANALYSIS OF Algorithm

Part 2

Implement the following accelerated version of Euclid's algorithm for gcd(s, t) with precondition 0 < s <= t. Use the programming conventions outlined in the online materials and the format below. Include preconditions, postconditions, and outcomes. Recall that outcomes must accumulate, so prior outcomes must be restored. Favor loops of the form while(!outcome) because they are readily verifiable. Explain efficiency as requested below.

Increment k until s^k <= t and s^k+1 > t, retaining s², s³, ... s^k. Diminish t by s^k. If (the new) t is still the larger of s and t, iterate down s², s³, ... s^k starting with s^k, repeating the process of finding the highest power of s to subtract from t. If the new t is the smaller of s and t, switch the roles.

For example, to find gcd(4, 250), s=4, and we consider 4, 4²=16, 64, 256. We subtract 64 from 250. The new t is 186. We start by considering 256which is too big to subtract from 250then 64. We subtract 64 from 186, getting 122 for t, and repeat the process. So we go from gcd(4, 250) to gcd(4, 186) to gcd(4, 122) to gcd(4, 58) to gcd(4, 42) to gcd(4, 26) to gcd(4, 10) to gcd(4, 6) to gcd(4, 2) to gcd(2, 2) = 2. There was a switching of roles in the digits in the last step.

Part 2.1 Efficiency: n

What is n in this case? Explain

NB: There are two ways of doing the Euclidean algorithm and it is expected that students will use subtraction method for comparison