Duelist1234's blog

Euclidean algorithm
By Duelist1234, history, 15 months 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?
»
15 months ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      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
»
15 months ago, # |
  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