GCD time complexity

Question

Solved: True

Help me how to calculate time complexity of GCD function:

Int GCD(int a, int b) {
While (b != 0) {
int tmp = a % b;
a = b;
b = tmp;
}
return a;
}

Answer 1

Bob_Li thanks, that was useful and I understood the answer:)

Answer 2

AraL what are you trying to do? Can you provide brief information?

Answer 3

Alhaaz this loop is not infinite, look at while condition, after some iterations, finally b variable will become 0 and then while will be end....

Answer 4

Alhaaz give some number to variables and trace it

Answer 5

AraL you want to find GCD(Greatest Common Division) right?

Here is the correct syntax: -

int GCD(){
while(a != b) {
if(a> b)
a-=b;
else
b-= a;
}
return a;
}

Answer 6

Alhaaz my question is finding time complexity of this code, I didn't mean I want a code to find GCD

Answer 7

Time complexity of this code is O(log(min(a,b)) but I don't know the way to find this time complexity

Answer 8

a >= b and a reduces with iteration, so it's log(min(a, b))

Answer 9

Sharpneli I can't understand, need more explanation

Answer 10

https://www.geeksforgeeks.org/understanding-time-complexity-simple-examples/

Answer 11

Bob_Li thanks, but it didn't help because finding the time complexity of this algorithm is almost different with algorithm that just use (+, -, *, ÷ ...)

Answer 12

ok, more specifically gcd:

https://www.geeksforgeeks.org/time-complexity-of-euclidean-algorithm/

https://math.stackexchange.com/questions/1552449/find-the-number-that-gives-the-max-number-of-steps-for-the-euclidean-algorithm

and people arguing about it here:
https://stackoverflow.com/questions/3980416/time-complexity-of-euclids-algorithm

but yes, I think Sharpneli's answer is the reasonable one.