help me to find complexity of gcd
Gcd time complexity
Hello @Faizan-Ali-1395131367301898
Consider any two steps of the Euclidean method to find GCD.
At some point, you have the numbers (a,b) with a>b. After the first step these turn to (b,c) with c=a%b, and after the second step the two numbers will be (c,d) with d=b%c.
Now think backwards. As d=b%c, we know that b=kc+d for some k>0. The smallest possibility is k=1, therefore b≥1c+d=c+d.
From that result and from a>b we get a>c+d. If we add the last two inequalities we just derived, we get that (a+b)>2(c+d).
In words, after each two consecutive steps the sum of the two numbers decreases to less than half of its original size.
This implies that the complexity is logarithmic