CODEWITHSUNDEEP
time-complexityeuclidean-algorithm
sara112
sara112

Reputation: 13

Time Complexity of Euclid Algorithm by Subtraction

 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?

Upvotes: 1

Views: 986

Answers (1)

Anatolii
Anatolii

Reputation: 14660

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.

Upvotes: 1

Related Questions