title: Time complexity of Euclid's Algorithm
body: <p>I am having difficulty deciding what the time complexity of Euclid's greatest common denominator algorithm is. This algorithm in pseudo-code is:</p>
  
  <pre><code>function gcd(a, b)
      while b ≠ 0
         t := b
         b := a mod b
         a := t
      return a
  </code></pre>
  
  <p>It seems to depend on <em>a</em> and <em>b</em>. My thinking is that the time complexity is O(a % b). Is that correct? Is there a better way to write that?</p>