CODEWITHSUNDEEP
algorithmtimeasymptotic-complexity
cparks10
cparks10

Reputation: 377

Running time of GCD Algorithm?

unsigned int gcd(unsigned int n, unsigned int m)
{
if (n == 0) 
    return m; 
if (m == 0) 
    return n; 

while (m! = n)
{
if (n > m) 
    n = n − m; 
else 
    m = m − n;
}
return n;
}

Some psuedocode for an iterative GCD algorithm using a while loop. I there are no places where there is anything being divided by 2, so I do not think that it is logarithmic. Since the while loop runs for a time directly proportional to N does it make it linear like O(N)?

Upvotes: 0

Views: 159

Answers (1)

MK.
MK.

Reputation: 34527

I would say it is O(max(n,m)) because it big-O should be symmetric for n vs m since the algorithm is. @PaulHankin improves this to be O(max(n,m)/gcd(n,m)).

Upvotes: 1

Related Questions