title: time complexity of below gcd algorithm
body: <p><strong>I have been finding it difficult to calculate the time complexity of The binary GCD algorithm, also known as Stein's algorithm which is given to be  O(n^2) where n is the number of bits in the larger of the two numbers.
  Shouldn't it be O(n) ?</strong>
  Algorithm is as below :</p>
  
  <p>1.gcd(0, v) = v, because everything divides zero, and v is the largest number that divides v. Similarly, gcd(u, 0) = u. gcd(0, 0) is not typically defined, but it is convenient to set gcd(0, 0) = 0.</p>
  
  <p>2.If u and v are both even, then gcd(u, v) = 2·gcd(u/2, v/2), because 2 is a common divisor.</p>
  
  <p>3.If u is even and v is odd, then gcd(u, v) = gcd(u/2, v), because 2 is not a common divisor. Similarly, if u is odd and v is even, then gcd(u, v) = gcd(u, v/2).</p>
  
  <p>4.If u and v are both odd, and u ≥ v, then gcd(u, v) = gcd((u − v)/2, v). If both are odd and u &lt; v, then gcd(u, v) = gcd((v − u)/2, u). These are combinations of one step of the simple Euclidean algorithm, which uses subtraction at each step, and an application of step 3 above. The division by 2 results in an integer because the difference of two odd numbers is even.[3]</p>
  
  <p>5.Repeat steps 2–4 until u = v, or (one more step) until u = 0. In either case, the GCD is 2kv, where k is the number of common factors of 2 found in step 2.</p>