0
GCD time complexity
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; }
8 Answers
0
AraL what are you trying to do? Can you provide brief information?
0
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....
0
Alhaaz give some number to variables and trace it
0
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;
}
0
Alhaaz my question is finding time complexity of this code, I didn't mean I want a code to find GCD
0
Time complexity of this code is O(log(min(a,b)) but I don't know the way to find this time complexity
0
a >= b and a reduces with iteration, so it's log(min(a, b))
0
Sharpneli I can't understand, need more explanation