What is the big-o notation of these loops int gcd1(int m, int n) { int gcd = 1;

Question

What is the big-o notation of these loops

int gcd1(int m, int n)
{
int gcd = 1;
for (int k = 2; k <= m && k <= n; k++)
{
if (m % k == 0 && n % k == 0)
gcd = k;
}
return gcd;
}

/////////// B
int gcd2(int m, int n)
{
int gcd =1;
for (int k = n; k >= 1; k--)
{
if (m % k == 0 && n % k == 0)
{
gcd = k;
break;
}
}
return gcd;
}

////C
int gcd3(int m, int n)
{
int gcd = 1;
if (m == n) return m;
for (int k = n / 2; k >= 1; k--)
{
if (m % k == 0 && n % k == 0)
{
gcd = k;
break;
}
}
return gcd;
}

//////// D

int gcd4(int m, int n)
{
if (m % n == 0)
return n;
else
return gcd4(n, m % n);
}

Explanation / Answer

A) Time complexity is O(min(m,n))
B) Time complexity is O(n)
C) Time complexity is O(n/2)
D) Time complexity is O(logn)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.