Complexity of the Euclidean Algorithm (2/7) • The complexity of an algorithm is the approximate number of steps necessary for the algorithm to finish as a function of the size of the input. • Most commonly we are interested in either average case complexity or worst case complexity. These mean exactly what they sound like. • We shall now analyze the worst case complexity of the Euclidean Algorithm (EA). EA Worst Case • The EA will take the longest if each remainder is not much smaller than the previous remainder. • Said another way, EA will take the longest if the quotients qk are relatively small. In particular, the worst case is going to occur when every quotient is 1 ! • So, what does the EA sequence look like if every quotient is 1: (Recall: r-1 = a and r0 = b.) • r-1 = r0 + r1 r0 = r1 + r2 r1 = r2 + r3 ......... rn-2 = rn-1 + rn EA Worst Case Continued • For simplicity, let’s assume n is even (easy to adjust if • • • • odd), where rn is the last non-zero remainder. From above we have then: b = r1 + r2 > 2r2 , r2 = r3 + r4 > 2r4, r4 = r5 + r6 > 2r6, etc., and finally rn-2 = rn-1 + rn > 2rn . Combining all these, we get b > 2n/2 rn 2n/2 . Now solve this equation for n. (How do you solve equations for things in the exponent?) Finally, change the base-2 log to a base-10 log, since base10 logs reveal the number of decimal digits. (Discuss.) Conclusion: • Theorem. The worst case complexity for the Euclidean Algorithm is that it will complete in a number of steps which is at most about 6.7 times the number of decimal digits in b. • Finally, are there pairs of numbers which have the property that this worst case occurs when you apply the EA to them to get their GCD? • Answer: Yes! Consider the Fibonacci Numbers. • For Monday, absorb these ideas!!