2 votes 2 votes What is the worst case time complexity to find the gcd(m,n) using best algorithm known? A. O(log(min(m,n))) B, O(log(max(m,n))) Algorithms algorithms time-complexity + – Vikrant Singh asked Jan 31, 2015 • edited Jun 26, 2022 by makhdoom ghaya Vikrant Singh 1.7k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply S Ram commented Jan 15, 2017 reply Follow Share Can u explain how B is answer? 0 votes 0 votes junaid ahmad commented Oct 10, 2017 reply Follow Share https://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes option a for Euclid algorithm Sushil Verma answered Feb 25, 2015 Sushil Verma comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Check http://mathworld.wolfram.com/EuclideanAlgorithm.html Lamé showed that the number of steps needed to arrive at the greatest common divisor for two numbers less than n is So O(log min(a, b)) is a good upper bound. Bipin answered Sep 29, 2015 Bipin comment Share Follow See all 0 reply Please log in or register to add a comment.
