Duelist1234's blog

Euclidean algorithm
By Duelist1234, history, 2 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

»
2 months ago, # |
  Vote: I like it -15 Vote: I do not like it

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

→ Reply
  • »
    »
    2 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
»
2 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
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Euclidean algorithm's time complexity is often denoted as O(log(min(a,b))).

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Duelist1234 (previous revision, new revision, compare).

→ Reply