A Word about O

What is "computational cost?"

Searching a List

Searching a Sorted List

Euclid's Algorithm

Theorem Suppose that a, b, q and r are integers and that b = a*q + r. Then gcd(a,b) = gcd(a,r)

Proof

Slow way to compute GCDs.

Mucho Quicker Way