Duelist1234's blog

Euclidean algorithm
By Duelist1234, history, 3 years ago, In English

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.

  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it -15 Vote: I do not like it

$$$gcd(a, b)$$$ works in $$$log(a) + log(b)$$$ time

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

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!

→ Reply