The link listed for the time complexity proof of Eucledian distance mentions that if b>=a/2 then a,b = b,a%b and b becomes at most half of it’s previous value. Could anybody elaborate that? How this conclusion is reached?
The link listed for the time complexity proof of Eucledian distance mentions that if b>=a/2 then a,b = b,a%b and b becomes at most half of it’s previous value. Could anybody elaborate that? How this conclusion is reached?