Time Complexity of Euclid Algorithm by Subtraction

Question

 int gcd(int a, int b)
{
    while(a!=b)
    {
        if(a > b)
            a = a - b;
        else
            b = b - a; 
    }

    return a;
}

What is the time complexity of this algorithm? Can someone provide a detailed explanation?

@templatetypedef nope, for Euclid Algorithm by Subtraction, a and b must be positive integer numbers. — Anatolii
– Anatolii, Commented May 13, 2021 at 19:52
@Anatolii Wouldn't it be trivial to modify the algorithm to handle one of the inputs being zero? — templatetypedef
– templatetypedef, Commented May 13, 2021 at 19:54
@templatetypedef Sure, you're right, but I do not know what exact requirements the OP has. At least, the OP could use an unsigned type for parameters and function return type. — Anatolii
– Anatolii, Commented May 13, 2021 at 20:09

Anatolii · Accepted Answer · 2021-05-13 20:07:00Z

1

For Euclid Algorithm by Subtraction, a and b are positive integers.

The worst case scenario is if a = n and b = 1. Then, it will take n - 1 steps to calculate the GCD. Hence, the time complexity is O(max(a,b)) or O(n) (if it's calculated in regards to the number of iterations).

By the way, you should also fix your function so that it validates whether a and b are really positive integer numbers. Or even better, you could change your return and parameter types to unsigned long or unsigned int or similar and, as suggested by @templatetypedef, handle cases for a = 0 or b = 0 separately.

edited May 13, 2021 at 20:07

answered May 13, 2021 at 19:51

Anatolii

14.8k5 gold badges38 silver badges70 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Time Complexity of Euclid Algorithm by Subtraction

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related