Ans :
In function gcd(m,n), each iteration of while loop has one test condition, one division
and two assignment that will take constant time. Hence number of times while loop
will execute will determine the complexity of the algorithm. Here it can be observed
that in subsequent steps, remainder in each step is smaller than its divisor i.e smaller
than previous divisor. The division process will definitely terminate after certain
number of steps or until remainder becomes 0.
Best Case
If m=n then there will be only one iteration and it will take constant time i.e O(1)
Worst Case
If n=1 then there will be m iterations and complexity will be O(m)
If m=1 then there will be n iterations and complexity will be O(n)
Average Case
By Euclid‟s algorithm it is observed that GCD(m,n) = GCD(n,m mod n) = GCD(m mod n, n mod (m mod n))
Since m mod n = r such that m = nq + r, it follows that r < n, so m > 2r. So after every two iterations, the larger number is reduced by at least a factor of 2 so there are at most O(log n) iterations.
Complexity will be O(log n), where n is either the larger or the smaller number.
