4. In mathematics GCD or Greatest Common Divisor of two or more integers is the
ID: 3908849 • Letter: 4
Question
4. In mathematics GCD or Greatest Common Divisor of two or more integers is the largest positive integer that divides both the number without leaving any remainder. Example: GCD of 20 and 8 is 4 Write a recursive algorithm, using Euclid's, to find the GCD of any 2 numbers, e g. GCD(120,144) 5. For each of the function answer from the following. FIN) given below, indicate the tightest bound possible, choose you O(N'), O(N),O(NS), O(N'), o(1),onN*), o12"), etc a. FIN)-N. (100N + 200N3)+N3 c. F(N)-400N2-2ON d. F(N) -(N/4)+ N/2 e. FIN)-(N+N+N+ N) f. FIN) (N.N.N)Explanation / Answer
4. The algorithm is based on below facts.
CODE
================
// C program to demonstrate Basic Euclidean Algorithm
#include <stdio.h>
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}
// Driver program to test above function
int main()
{
int a = 10, b = 15;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 35, b = 10;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 31, b = 2;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
return 0;
}
5.
Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
a) F(N) = N.(100N + 200N3) + N3 = 100N2 + 200N4 + N3 = O(N4)
b) F(N) = N2 + N = O(N)
c) F(N) = O(N2)
d) F(N) = O(N)
e) F(N) = 16N2 = O(N2)
f) F(N) = N6 = O(N6)
// C program to demonstrate Basic Euclidean Algorithm
#include <stdio.h>
// Function to return gcd of a and b
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}
// Driver program to test above function
int main()
{
int a = 10, b = 15;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 35, b = 10;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
a = 31, b = 2;
printf("GCD(%d, %d) = %dn", a, b, gcd(a, b));
return 0;
}
5.
Big O Notation: The Big O notation defines an upper bound of an algorithm, it bounds a function only from above.
O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 <= f(n) <= cg(n) for all n >= n0} a) F(N) = N.(100N + 200N3) + N3 = 100N2 + 200N4 + N3 = O(N4)
b) F(N) = N2 + N = O(N)
c) F(N) = O(N2)
d) F(N) = O(N)
e) F(N) = 16N2 = O(N2)
f) F(N) = N6 = O(N6)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.