Running Time of GCD Function Recursively (Euclid Algorithm)

Question

I have only been able to find posts about how to implement the gcd function both recursively and iteratively, however I could not find this one. I am sure it's on Stackoverflow however I could not find it so I apologize if it's a duplicate post.

---

I have looked at the analysis on Wikipedia (here) and could not understand their recurrence relation.

Consider the following implementation of the GCD function recursively implemented in C. It has a pre condition that both numbers must be positive, however irrelevant for the run time.

int gcd( int const a, int const b ) {
  // Checks pre conditions.
  assert( a >= 0 );
  assert( b >= 0 );

  if ( a < b ) return gcd( b, a );

  if ( b == 0 ) return a;

  return gcd( b, a % b );
}

Performing an analysis on the run time I find that every operation is O(1) and hence we know the recurrence relation thus far is: T(n) = O(1) + ???. Now to analyze the recursive call, I am not sure how to interpret a (mod b) as my recursive call to properly state my recurrence relation.

Answer 1

At each recursive step, gcd will cut one of the arguments in half (at most). To see this, look at these two cases:

If b >= a/2 then on the next step you'll have a' = b and b' < a/2 since the % operation will remove b or more from a.

If b < a/2 then on the next step you'll have a' = b and b' < a/2 since the % operation can return at most b - 1.

So on each recursive step, gcd will cut one of the arguments in half (at most). This is O(log(N)) steps where N is the max of the initial a and b.

Answer 2

To analyze Euclidean GCD, you ought to use Fibonacci pairs: gcd(Fib[n], Fib[n - 1]) - Worst case scenario.

If you test your Euclidean GCD above, you'll end up with 24 recursive calls.

If you're accustomed to recurrence relations solving, the following might interest you:

With this study, one can't deduce the exact number of iterations for any dividend/divisor pair (hence the small Oh notation), but it guarantees that this upper bound is valid. Generally, the lower bound is Omega(1) (When the divisor is 1, for instance).

Answer 3

A simple analysis and proof goes like this:

1. Show that if Euclid(a,b) takes more than N steps, then a>=F(n+1) and b>=F(n), where F(i) is the ith Fibonacci number.
   This can easily be done by Induction.

2. Show that F(n) ≥ φ^n-1, again by Induction.

3. Using results of Step 1 and 2, we have b ≥ F(n) ≥ φ^n-1
   Taking logarithm on both sides, log_φb ≥ n-1.
   
   Hence proved, n ≤ 1 + log_φb

This bound can be improved.
No. of recursive calls in EUCLID(ka,kb) is the same as in EUCLID(a,b), where k is some integer.

Hence, the bound is improved to 1 + log_φ( b / gcd(a,b) ).