Design and Analysis of Algorithms20795 marksBasic Algorithms
Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity.
Explain the iterative algorithm to find the GCD of given two numbers and analyze its complexity. [5]
The GCD (Greatest Common Divisor) of two numbers is found using the iterative Euclidean algorithm based on the property that GCD(m, n) = GCD(n, m mod n). Steps: Pseudocode: --- Find GCD(48, 18): Step m n r = m mod n --------------------------- 1 48 18 48 mod 18 = 12 2 18 12 18 mod 12 = 6 3 12 6 1...