1) What is the order of the following algorithm:
procedure Func1(m,n)
{
while (m > 0)
{
t = n mod m;
n = m;
m = t;
}
}
(Select the answer from the following options and prove yourchoice):
a) theta (ln m)
b) m^2
c) n^m
d) m^n
PLEASE EXPLAIN IT IN DETAIL
Answer
This is a GCD algorithm.every time through the loop value of m and n change by a factor of smaller of m, nso, total number of iterations = O(ln m)
Answer: a) theta (ln m)