GCD time complexity

Question

Solved: false

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

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

Answer 2

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 3

Alhaaz give some number to variables and trace it

Answer 4

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 5

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

Answer 6

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

Answer 7

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

Answer 8

Sharpneli I can't understand, need more explanation