This algorithm's complexity is correct?

Question

The algorithm I do not understand is :

alg(m, n)
1. if m>n then
2.     return alg(m-n, n)
3. else
4.     if n>m then
5.          return alg(n, m)
6.     else
7.          return n

I think that the recurrence formula is T(m) = T(m-n) + a, where a is a constant. I tried to do a substitution:

T(m) = T(m-k) + a*n

Assume that

k=m => T(m) = T(0) + a*n => T(m) = n*a + 1 => The complexity is O(n).

Please tell me if I am wrong. Thank you!

Answer 1

I searched on the Internet and the complexity of this algorithm is O(n+m). I am posting this to help other people. The link is: https://codility.com/media/train/10-Gcd.pdf