Duelist1234's blog

By Duelist1234, history, 10 months ago,

What is the time complexity of the Euclidean Algorithm? Also please upvote im really down bad with the downvotes and i want to return to positive contribution. Edit: When i meant the contribution i was hoping to get massivly downvoted.

• -12

 » 10 months ago, # |   -15 $gcd(a, b)$ works in $log(a) + log(b)$ time
•  » » 10 months ago, # ^ |   0 I see my comment got downvoted:( Can somebody please explain why it is $log(min(a, b))$? I always thought that every step one of the variables is decreased at least two times. Why am I wrong?
 » 10 months ago, # |   +18 Short answer: log(min(a, b)).Long answer: Stack Overflow my beloved There are multiple explanations for why the time complexity may or may not be something. The case when A and B are very large numbers is also tackled. Really cool!
 » 10 months ago, # |   0 Euclidean algorithm's time complexity is often denoted as O(log(min(a,b))).
 » 10 months ago, # |   0 Auto comment: topic has been updated by Duelist1234 (previous revision, new revision, compare).