How to solve the recursion of this algorithm?

Question

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

I solved it 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 solve this problem.

Answer 1

The problem here is that the size of the next values ​​of m and n depends on what the previous values ​​were, and not just their size. Knut details this in The Art of Programming. Volume 2: Seven-Dimensional Algorithms, Section 4.5.3. After about five pages, he will prove that you might have guessed that in the worst case, when m and n are consecutive fibonacci numbers. From this (or otherwise!) It turns out that in the worst case the number of required divisions is linear in the logarithm of the larger of the two arguments.

After much more complex mathematics, Knuth proves that the middle case is also linear in the logarithm of the arguments.

Answer 2

mcdowella gave an excellent answer to this.

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

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

It can be shown as

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

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

Thus, you halve the larger input, and in two calls, both arguments will be halved.