Search code examples
time-complexityeuclidean-algorithm

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?

Solution

  • 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.