CODEWITHSUNDEEP
algorithmrecursion
devsda
devsda

Reputation: 4222

how to solve recursion of given algorithm?

int gcd(n,m)
{
  if (n%m ==0) return m;
  n = n%m;
  return gcd(m,n);
}

I solved this and i got 

T(n, m) = 1 + T(m, n%m)  if n > m
        = 1 + T(m, n)    if n < m
        = m              if n%m == 0

I am confused how to proceed further to get the final result. Please help me to solve this.

Upvotes: 4

Views: 195

Answers (2)

sukunrt
sukunrt

Reputation: 1543

mcdowella has given a perfect answer to this.

For an intuitive explaination you can think of it this way,

if n >= m, n mod m < n/2;

This can be shown as,

if m < n/2, then: n mod m < m < n/2

if m > n/2, then: n mod m = n-m < n/2

So effectively you are halving the larger input, and in two calls both the arguments will be halved.

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

The problem here is that the size of the next values of m and n depend on exactly what the previous values were, not just their size. Knuth goes into this in detail in "The Art of Computer Programming" Vol 2: Seminumerical algorithms, section 4.5.3. After about five pages he proves what you might have guessed, which is that the worst case is when m and n are consecutive fibonacci numbers. From this (or otherwise!) it turns out that in the worst case the number of divisions required is linear in the logarithm of the larger of the two arguments.

After a great deal more heavy-duty math, Knuth proves that the average case is also linear in the logarithm of the arguments.

Upvotes: 7

Related Questions