Time complexity of GCD algorithm

Question

gcd(n,m) {
  r = n%m
  if r == 0 return m;
  // else
  return gcd(m, r)
}

Answer 1

Below is my attempt at it approaching the algorithm using the Euclidean algorithm. If there's a weak link to this proof, it's probably proving the GCD algorithm is the Euclidean algorithm, or at least behaves similarly. I apologize if the image below taken from pdf is either too large or too small to read. 

Answer 2

So for the simple observation. Assume gcd(a,b), I find that the digit of the number being divided will be decreased within two steps at most. So the digit of the number is represented by log₁₀a, then the total step T(a,b) is 2log₁₀a which is O(loga). 

Comments

Maybe easier to express this in terms of log base 2.  Also, what is the recurrence relation?

Answer 3

Hi all,

After research I found my answer as following:

this problem is also called the Euclidian analysis. The worst case in this problem is that the two number n and m are the consecutive Fibonacci numbers F_n+1 and F_n because it will continue calculating gcd(F_n+1, F_n) = gcd(F_n, F_n-1)

assume that T(a,b) is the steps we need to calculate gcd(a,b)

We know that F_n = O(Øⁿ). and lim_n->infi(F_n+1/F_n) = Ø   // Ø is the golden ratio

 So T(F_n+1, F_n) = n; 

T(a,b) = OT(a, Fn) = OT(F_n+1, F_n)

So T(a,b) = O(log_Øb)

Another way to solve this problem is to use the "decreasing factor" introduced by Dr. Kiyoko F Aoki Kinoshita

decreasing factor is defined by d = a/a%b

from the analyse above we know that the main role played among T(a,b) is b

Thus T(a,b) = O(log_d​b)

actually there are lots of other methods to resolve this, just list two for reference.

Hope this do any help

Ken

Comments

I would like a simple proof of the time complexity first.  Discussion about Fibonacci numbers is relevant, but not central or required for that simple proof.