gcd algorithm time complexity

Question

int gcd(int a, int b){
  if (a==b) return (a);
  else
  {
     if (a > b) return (gcd(b, a-b));
     else return (gcd(a, b-a));
  }
}

I found that the complexity of this algorithm is T(n)= 2T(n-1)+5 is that correct? and if it is how can I apply the Master theorem in order to find the time complexity class?

No. T() formula is not complexity - it is recursive equation to find complexity. And T(n) here does not relate to T(n-1). Master theorem is not applicable here — MBo, Aug 04 '20 at 09:21
Does this answer your question? [Time complexity of Euclid's Algorithm](https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm) — Yash Shah, Aug 04 '20 at 09:22
@MBo do you know how to find the worst-case complexity of this algorithm? — Alex Pol, Aug 04 '20 at 09:29
@YashShah your answer includes mod which is not the same algorithm so I think the complexity is different — Alex Pol, Aug 04 '20 at 09:34
Real complexity might be more complex - when we made a/b steps for a>b, we need to repeat with `b, a mod b` and so on — MBo, Aug 04 '20 at 09:38
@YashShah: no it does not answer the question. This link is misleading ! — , Aug 04 '20 at 10:02
@MBo Max(a,b)/Min(a,b) this would imply, that it is faster, when the inputs are similar size and slower, when they are very different. But both cases are equally bad. — jjj, Aug 04 '20 at 10:27

score 0 · Answer 1 · answered Aug 04 '20 at 10:31

0

You don't define n and the time complexity of the algorithm does not depend on a single parameter.

For instance, assuming that n = max(a, b), we have

T(a, a) = O(1)

T(a, 1) = O(n).

answered Aug 04 '20 at 10:31

jjj · Answer 2 · 2020-08-04T10:32:33.837

complexity of this algorithm is T(n)= 2T(n-1)+5 is that correct?

No, it is not. You only have one recursive call and don't split the problem into 2 smaller problems, as your formula implies.

You can't use the Master Theorem, when you have something like T(n)=aT(n-1)+f(n), you need T(n)=aT(n/b)+f(n) instead. So you have to divide the problem size by the same value every recursive call.

For this version the time complexity is O(n), where n = max(a,b) or n=a+b. You worst case is when you input gcd(n,n+1) or gcd(1,n) then you just subtract 1 n-1 times.

In the best case (where inputs are not the same) you input two successive fibonacci numbers, then you get logarithmic complexity. This best case for subtraction version is the same case as the worst case for modulus version of euclids algorithm. In fact, in this case there is no difference between them.

The Time complexity of Euclids algorithm with modulo is O(log(n)), where n = max(a,b) or n=a+b. You can get this complexity, when you have a look at the fibonacci numbers. They are the worst case for this algorithm and they grow exponentially. Euclids algoritm goes (backwards, direction does not matter) over this numbers, so the complexity is the inverse of the exponential function, so log(n) (base does not matter)

My downvote because 1) there is no `n` in the algorithm, and 2) the complexity of this version is `O(a+b)`. Don't answer blindly. — , Aug 04 '20 at 10:01
@YvesDaoust you normally let n be the greatest input value. But I added it now. — jjj, Aug 04 '20 at 10:04

gcd algorithm time complexity

2 Answers2